Skip to main content

All Questions

Filter by
Sorted by
Tagged with
47 votes
4 answers
10k 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, ...
Harrison Brown's user avatar
25 votes
1 answer
596 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 ...
Nate's user avatar
  • 2,242
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 ...
Joseph O'Rourke's user avatar
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 ...
Dr Shello's user avatar
  • 1,180
12 votes
3 answers
582 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 ...
domotorp's user avatar
  • 18.7k
11 votes
2 answers
2k views

Given a graph embedded on a torus, how many edges are necessary for noncontractible loops to be long?

If we are given a graph embedded on a torus, with the following properties, what is the minimum number of edges it can have? Any noncontractible loop is comprised of at least n edges. Any ...
Graham's user avatar
  • 111
10 votes
1 answer
369 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 ...
Ghodrati's user avatar
  • 175
10 votes
1 answer
312 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$. ...
Tony Huynh's user avatar
  • 32.1k
9 votes
3 answers
2k 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 ...
Pavan Sangha's user avatar
9 votes
0 answers
1k views

Simplicial Representations of (Hyper)Graph Complexes

For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, ...
Gwyn Whieldon's user avatar
8 votes
2 answers
615 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 ...
Lfmoamse's user avatar
6 votes
1 answer
142 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 ...
M. Winter's user avatar
  • 13.6k
5 votes
1 answer
479 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 ...
Hauke Reddmann's user avatar
5 votes
0 answers
83 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 ...
M. Winter's user avatar
  • 13.6k
4 votes
2 answers
232 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 ...
Turbo's user avatar
  • 13.9k
4 votes
1 answer
214 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., ...
Licheng Zhang's user avatar
4 votes
2 answers
266 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 ...
user avatar
4 votes
1 answer
540 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, ...
user avatar
3 votes
1 answer
163 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: ...
Johnny Cage's user avatar
  • 1,561
3 votes
1 answer
215 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 ...
Pavan Sangha's user avatar
3 votes
0 answers
94 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 $...
Jacob.Z.Lee's user avatar
2 votes
1 answer
319 views

Why are graph embeddings defined the way they are?

In my recent question I asked about a proof for the fact that the dual of a dual graph embedding is equal to the original graph. Thinking about this a little more leads me to wonder why graph ...
Nick Salter's user avatar
  • 2,830
2 votes
2 answers
413 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 ...
Kristaps John Balodis's user avatar
2 votes
1 answer
121 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 ...
Pavan Sangha's user avatar
2 votes
1 answer
137 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 ...
Pavan Sangha's user avatar
2 votes
1 answer
238 views

Maximum fixed genus Bipartite graphs

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with $n$ vertices of color $1$ and with $n$ vertices of color $2$. What is the maximum number of edges that a genus $g$ graph $B_{n,n}$ can have? ...
Turbo's user avatar
  • 13.9k
2 votes
1 answer
401 views

Obstructions to genus $g+1$ bipartite graph having genus $g$

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices. Say I know $g \le \operatorname{genus}(B_{n,n}) \le g+1$. What obstructions prevent $B_{n,n}$ from being ...
2 votes
1 answer
111 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 ...
GMB's user avatar
  • 1,389
2 votes
0 answers
215 views

Polyhedral embeddings of large face-width where all faces have the same length

Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length? By polyhedral embedding I mean an embedding of the graph on a ...
valle's user avatar
  • 884
1 vote
1 answer
194 views

Bounds on lengths of intervals in bounded-degree interval graphs

A graph is said to be an interval graph if its vertices can be associated with (closed) intervals on the real line $\mathbb R$ and there is an edge between two vertices if and only if the ...
Pranay Gorantla's user avatar
1 vote
1 answer
115 views

Bounds on lengths of boxes in bounded-degree box graphs

$\DeclareMathOperator{\box}{\operatorname{box}}$$\DeclareMathOperator{\cub}{\operatorname{cub}}$ This is a follow up and an extension of another question I asked recently. A box graph is a graph ...
Pranay Gorantla's user avatar
1 vote
0 answers
42 views

What lower bounds are known for pair crossing number and related questions in multigraphs?

So in terms of crossing number https://arxiv.org/pdf/1808.10480 gives a lower bound of $O(e^{2.5}/n^{1.5})$ for multigraphs with no face of length 2 with no node contained inside. What do we know ...
Hao S's user avatar
  • 111
1 vote
0 answers
33 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" ...
DavidHume's user avatar
  • 743
1 vote
0 answers
123 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 ...
Pavan Sangha's user avatar
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 ...
vidyarthi's user avatar
  • 2,089