Questions tagged [topological-graph-theory]

Graph theoretical questions with a topological flavour. For example, graphs on surfaces, spatial embeddings, and geometric graphs. Use the graph-drawing tag for questions specific to graph drawing (e.g. crossing numbers).

Filter by
Sorted by
Tagged with
10 votes
1 answer
259 views

Do triple-linked graphs exist?

Lets say that a finite simple graph $G$ is (intrinsically) fully triple-linked if for each embedding of $G$ into $\Bbb R^3$ we can find three disjoint cycles $C_1,C_2,C_3\subset G$ whose embeddings ...
3 votes
2 answers
105 views

Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?

For a graph of genus $g$, it holds that it cannot have too many disjoint 5-cliques, as each clique requires a new handle. It feels that given a graph of genus $g$, it cannot have an unbounded number ...
0 votes
0 answers
23 views

Building hypercubes from the bottom up

let $H^k$ denote a $k$-dimensional hypercube in a complete symmetric graph $G(V,E)$ without self-loops and parallel edges; let $|V|=2^n$ be the number of vertices. setting $\mathbb{H}^0 := V$, i.e. ...
3 votes
1 answer
133 views

Conditions on graphs to assure unique embedding on a fixed genus surface

The classical Whitney Theorem in low topological theory/graph theory states that every 3-connected planar graph is uniquely embeddable (up to orientation) on the sphere. My question is the following: ...
5 votes
0 answers
79 views

When does the ΔY-family of a simple graph contain multigraphs?

Given a graph $G$, its ΔY-family is the smallest family of graphs that contains $G$ and is closed under ΔY- and YΔ-transformations. Since YΔ-transformations can introduce multi-edges, the ΔY-family of ...
6 votes
0 answers
132 views

Graph-theoretic quasi-crystals?

I have recently been interested in the following purely graph-theoretic notion that weakens the assumption of transitivity in a similar way to how quasi-crystals have "(possibly) aperiodic long-...
4 votes
0 answers
58 views

Which cellular embeddings of Eulerian graphs have bipartite duals?

It is well-known that a plane graph $G$ is Eulerian if and only if its (geometric) dual $G^*$ is bipartite. I am interested in generalisations of this result to cellular embeddings of Eulerian graphs ...
4 votes
1 answer
185 views

Find all 2-planar drawings of $K_6$ and $K_7$

A $k$-planar graph is a graph which can be embedded with at most $k$ crossings per edge. It is proved that a complete graph $K_n$ is 2-planar if and only if $n\le 7$. Angelini P., Bekos M. A., ...
10 votes
1 answer
302 views

Is this drawing of $K_{4,4}$ knotted?

Let $A$ and $B$ be skew lines in $\mathbb{R}^3$. Choose four points $a_1, a_2, a_3, a_4$ on $A$ and four points $b_1, b_2, b_3, b_4$. For all $i,j \in [4]$ draw a line segment from $a_i$ to $b_j$. ...
4 votes
1 answer
363 views

Example to show pairwise crossing number is not equal to crossing number

A common point of two edges in a graph drawing that is not an incident vertex is called a crossing. The crossing number $cr(G)$ is defined to be the minimum number of crossings in any drawing of $G$....
5 votes
1 answer
130 views

Embedding linklessly embeddable graphs without Borromean rings

A linklessly embeddable graph is a graph which can be embedded into $\Bbb R^3$ so that no two of its cycles are linked. For example, the Petersen graph is not such a graph. Now, I can think of another ...
1 vote
0 answers
32 views

Arranging bounded degree graphs into grids with few edges connecting horizontal and vertical lines

The following question arose when I was trying to find explicit topological embeddings of bounded degree graphs into $\mathbb R^3$ which match (asymptotically) the minimal possible "volume" ...
9 votes
3 answers
1k views

Embedding planar graphs into the grid

I've seen the following lemma in a paper. The result is by Valiant. A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...
24 votes
3 answers
2k views

Gauss-Bonnet Theorem for Graphs?

One can define the Euler characteristic χ for a graph as the number of vertices minus the number of edges. Thus an $n$-cycle has $\chi = 0$ and $K_4$ has $\chi=-2$. Is there an analog for the ...
5 votes
1 answer
476 views

Can all crossings in a graph be moved to one point?

Consider a graph $G$ with at least two unavoidable crossings, say, the disjoint union of two copies of $K_5$. Can such a graph always be drawn so that there is only one singular point (where all ...
6 votes
0 answers
74 views

Implications of combinatorial results towards discrete function theory on circle packings

Spurred primarily by a conjecture of Thurston in 1985, there was a series of developments in creating a "discrete analytic function" theory for maps between circle packings of complex ...
20 votes
4 answers
2k views

Cayley graph of $A_5$ with generators $(1,2,3,4,5),(1,4,3,2,5)$

The Cayley graph of $A_5$ with two generators of order 5 seems rather complicated. What is its graph genus (orientable or non-orientable)? The best I could get by trial and error is an embedding ...
1 vote
1 answer
73 views

Positive type function on open subgroup

Let $\phi: G \rightarrow \mathbb{C}$ be a continuous function. We say that $\phi$ is positive type if $\sum_{i,j=1}^{n} c_i\bar{c_j}\phi(g_{j}^{-1}g_i)\geq 0$ for all $n \in N, c_i \in \mathbb{C}, g_i ...
2 votes
1 answer
100 views

Chromatic numbers of geometric duals to a fixed graph

A planar graph $G$ has some set of embeddings $\{E_\gamma:G \hookrightarrow R^2\}$. Each of these embeddings has associated with it a geometric dual graph $G^*_\gamma$. Using $\chi$ to denote ...
1 vote
1 answer
136 views

Chordless cycles and planarity in graphs

Let $\{C(G)\}$ be the set of chordless cycles of a graph $G$. Compare the cycles pairwise. Let $\{V\}$ represent the pairs which have exactly one vertex in common; and, let $\{P\}$ represent those ...
3 votes
0 answers
149 views

Genus of the graph complement

Suppose a simple undirected graph $G$ with $n$ vertices has (minimum) genus $g$. What is the genus of its complement? My intuitive guess is that the answer is something like $$\text{genus of }K_n - g$$...
3 votes
0 answers
93 views

The pagenumber of subdivision of a complete graph

A book embedding of a graph $G$ consists of placing the vertices of $G$ on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The book thickness $...
1 vote
0 answers
103 views

What is known about this generalization of planar dual?

So it is well known that given a planar graph, $G$, embedded in the plane (without edge crossing, so a planar embedding). One can construct the planar dual, $G^*$. What is perhaps slightly less well-...
24 votes
1 answer
565 views

Doubly periodic 4 color theorem?

Let $G$ be a graph embedded (without crossings) on a torus $T$. It's fairly well known that this implies the chromatic number of $G$ is at most 7. If I lift $G$ to the universal cover of $T$, we get a ...
12 votes
0 answers
206 views

Does there exist 2-planar graph with chromatic number 8 or 9 or 10

A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that ...
2 votes
0 answers
49 views

Book thickness of covering graph II

A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a ...
1 vote
1 answer
114 views

Bookthickness of covering space

A book embedding of a graph G consists of placing the vertices of G on a spine and assigning edges of the graph to pages so that edges in the same page do not cross each other. The page number is a ...
0 votes
0 answers
56 views

Are total graph of power of cycles homeomorphic to powers of cycles?

Is the total graph associated to powers of cycles homeomorphic to powers of cycles themselves? I think yes, because the total graph associated to cycles is homeomorphic to cycles(i think?)So, does ...
2 votes
1 answer
103 views

Genus for specific family of graphs

We are looking for graphs with certain properties that have a specific genus. We constructed a simple family, but now realised that we actually only have an upper bound for the genus. Is there an easy ...
10 votes
1 answer
360 views

Orientations of Planar Graphs

Let $G$ be a $2$-edge-connected graph drawn in the plane (such that the edges intersect only at the endpoints). I want to orient the edges of $G$ such that for each vertex $v$, there are no three ...
4 votes
0 answers
193 views

Similarities between isomorphism classes of homeomorphic directed graphs

To clarify, I'm speaking of homeomorphisms in a graph theoretic context, defined by subdivisions of arcs in a directed graph. A subdivision of an arc $(x,z)$ in a directed graph is obtained by ...
2 votes
1 answer
255 views

Loop of crosscaps and Euler characteristic

The first picture below has $v=12$ vertices, $e=16$ edges, and seems to have $k=4$ crosscaps (denoted by something like $\oplus$). The number of faces $f$ should satisfy $$v-e+f=2-k$$ which gives $f=2$...
2 votes
1 answer
110 views

Maximum genus of an abstract "cycle complex"

Let us define an abstract "cycle complex" as the following combinatorial object: it is $(V, C)$, where $V$ is a set of $n$ nodes, $C$ is a set of $c$ cyclically ordered subsets of $V$, each ...
1 vote
1 answer
114 views

On graph imbedding genus clarification

Given a graph the minimum genus $g$ is the minimum number of handles needed so that there an imbedding of the graph on the surface with no edge crossings. If the graph is of genus $g$ then is there ...
4 votes
2 answers
229 views

Number of non-equivalent graph embeddings

Given a graph $G$, there is a minimal integer $g$ associated with it which captures the minimum genus a surface needs to have so that $G$ embeds in the surface without edge crossings. Is there a way ...
12 votes
3 answers
576 views

Can we map every graph in the plane such that all induced cycles selfintersect?

Suppose we have a graph G. Is it true that we can map its vertices to the plane such that when connecting neighboring vertices with segments, then any induced cycle of G that has length at least 4 ...
2 votes
0 answers
27 views

(Cyclic) edge-connectivity for lifts of voltage graphs?

Can someone point me in the direction of what's known about edge connectivity (or, ideally, cyclic edge connectivity) of graphs which are lifts of voltage graphs? It seems like someone should have ...
4 votes
1 answer
523 views

Connection between connectivity and cohesion of a graph

Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path. A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...
9 votes
2 answers
12k views

Reporting all faces in a planar graph

Hi, I was looking to traverse a planar graph and report all the faces in the graph (vertices in either clockwise or counterclockwise order). I have build a random planar graph generator that creates a ...
21 votes
3 answers
2k views

Obstructions for embedding a graph on a surface of genus g

Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings. Is the ...
8 votes
2 answers
1k views

Spanning trees of plane graphs containing an edge of every face

I feel sure this must be known, but can I find it?? Which connected plane graphs (graphs drawn in the plane without crossings) have a spanning tree such that at least one edge of each face is in the ...
2 votes
2 answers
350 views

Decomposing a graph into n-cycles [closed]

Suppose I have a strongly $k-regular$ graph $G$, of size $v$, where every vertex is $N>0$ $n-cycles$, for $at least$ one value of $n$ that divides $v$. Can we cut edges from $G$ in such a way ...
2 votes
1 answer
115 views

Orthogonal embeddings and edge lengths

I'm interested in orthogonal embeddings of graphs into the 2-dimensional, i.e where vertices are placed at integer co-ordinates and edges are routed along the grid lines and are not allowed to ...
4 votes
2 answers
254 views

Asymptotics of list size in Robertson-Seymour theorem

A planar graph cannot have $K_5$ and $K_{3,3}$ as minors. Robertson-Seymour theorem generalizes this by stating for every genus $g$ there is a finite list of forbidden minor graphs that are ...
47 votes
4 answers
9k views

Why are planar graphs so exceptional?

As compared to classes of graphs embeddable in other surfaces. Some ways in which they're exceptional: Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...
1 vote
0 answers
116 views

Building an orthogonal embedding for a 4-planar graph

I'm interested in the following paper http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In particular i'm interested in the construction Valiant describes to prove that it is possible to ...
2 votes
1 answer
131 views

VLSI circuit embeddings

In the following paper by Valiant http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 ...
3 votes
1 answer
198 views

Construction of planar embedding

I'm reading the following paper on universality considerations in VLSI circuits http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf In Theorem 2 On the second page it states there exists ...
2 votes
4 answers
11k views

Graduate Schools for Graph Theory [closed]

I am a rising senior in a small liberal arts college, and I was wondering if anyone could suggest me good graduate schools for graph theory. My only exposure to graph theory has been the intro graph ...
8 votes
2 answers
603 views

Embedding of planar graphs

I've recently come across the following lemma. Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...