Skip to main content

All Questions

Filter by
Sorted by
Tagged with
-2 votes
0 answers
60 views

Can both conditions about vertex degrees hold true in a planar graph? [closed]

I am working on a problem about planar graphs and trying to understand if two statements can both be true at the same time. The problem states that for any planar graph with at least 3 or more ...
4 votes
0 answers
67 views

is a 4-connected planar graph still Hamiltonian after removing an edge?

We know that 4-connected planar graphs are Hamiltonian(by the known Tutte Theorem). Additionally, Thomas and Yu [1] proved that removing two vertices from a 4-connected planar graph still preserves ...
6 votes
2 answers
723 views

Threshold function for a graph not being planar

A graph property $\mathcal{P}$ is monotone increasing if $G\in \mathcal{P}$ implies $G+e \in \mathcal{P}$, i.e., adding an edge to a graph does not destroy the property. It is well-known that every ...
2 votes
1 answer
95 views

Dipping into sets of parallel edges in graph drawings

Given a multigraph embedded in the plane call a maximal set of parallel edges between $u,v$ such that only one of the induced faces contains nodes besides $u$ or $v$ a topologically parallel set (tell ...
2 votes
0 answers
86 views

Does there exist a 5-connected planar graph that is perfect?

I asked this question on math stack, but didn't get any response, so I ask it here. In a previous post, I proved that no 5-connected maximal planar graph is perfect. (A perfect graph is a graph $G$ ...
2 votes
0 answers
48 views

On planar graphs with specific spanning tree count and poly number of vertices

Given set $\mathcal T_n=\{0,1,3,4\dots,2^n-1\}$ (note there is no $2$) what is the minimum number of vertices $m$ needed in a planar graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
2 votes
0 answers
75 views

Is the chromatic number of every 7-connected 1-planar graph at most 5?

1-planar graphs were first studied by Ringel (1965), who showed that they can be colored with at most seven colors. Later, the precise number of colors needed to color these graphs, in the worst case, ...
3 votes
2 answers
725 views

The perfect matching problem of planar graph

We know that connectivity is closely related to the Hamiltonian of planar graphs. The most famous result is the Tutte theorem. Theorem (Tutte, 1956). A 4-connected planar graph has a Hamiltonian ...
1 vote
0 answers
97 views

Problem related to crossing number

Let $G$ be a graph embedded in the plane (with crossings). For $ F \subset E(G) $, denote by $c(F)$ the set of edges of $G$ that cross some edge in $F$. Denote $\delta(v)$ the set of edges with one ...
7 votes
1 answer
413 views

Has Plummer's open problem on the cyclic connectivity of planar graphs been solved?

$\DeclareMathOperator\cl{cl}$The cyclic edge connectivity $\cl(G)$ is the size of a smallest cyclic edge cut, i.e., a smallest edge cut $F$ such that $G-F$ has two connected components, each of which ...
6 votes
3 answers
530 views

Enumerating all inequivalent planar embeddings of a planar graph

Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ ...
1 vote
1 answer
114 views

Removing a face from 4-connected planar graph

After removing a face (vertices along with edges) of a 4-connected planar graph, is the remaining graph 4-connected? Alternatively under what conditions is this true?
1 vote
0 answers
77 views

Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?

Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $\operatorname{sim}(G)$, the simplification of $G$ contains $ m' \gg 3n $ edges. Call the set of ...
0 votes
0 answers
52 views

Are there 4-connected planar non-hamilton multi-graphs?

Tutte proved the famous result: Every planar 4-connected graph has a hamiltonian cycle. But I read in Section 111.6.5 on book Eulerian Graphs and Related Topics that the author Herbert Fleischner ...
3 votes
1 answer
158 views

Sharp upper bound of the number of edges for graphs of thickness two

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
7 votes
2 answers
1k views

Planar layouts of bipartite graphs

Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar. It would be very convenient if there was a ...
1 vote
1 answer
91 views

Generating 12-vertex plane graphs with 2 faces of degree 3 and all other faces of degree 4

My question may be similar to generating-21-vertex-4-regular-plane-graphs-with-8-faces-of-degree-3-and-15-face., but it has differences. The plane graphs I desire (without needing regularity) have ...
6 votes
1 answer
290 views

Generating 21-vertex 4-regular plane graphs with 8 faces of degree 3 and 15 faces of degree 4

Is there any way to generate all 4-regular plane graphs with 21 vertices, 8 faces of degree 3, and 15 faces of degree 4? If so, how many of these graphs are there and what are they?
7 votes
1 answer
300 views

The origin of a planar graph theorem of Steinitz and Rademacher

The subsequent statements are extracted from the article titled 'Generating r-regular graphs' (https://doi.org/10.1016/S0166-218X(02)00593-0). A well-known classical theorem of Steinitz and ...
2 votes
0 answers
63 views

What is the range of connectivity for maximal IC-planar graphs?

A graph is IC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share no common end vertex. A graph $G$ is maximal in a graph ...
7 votes
1 answer
2k views

Why $K_5$ and $K_{3,3}$?

Most people will have already guessed that this is about Kuratowski's theorem. The theorem states that every non-planar graph must contain a complete graph $K_5$ with five vertices or a complete ...
2 votes
0 answers
235 views

Injection of Catalan objects into 3-connected planar graphs

Let $C_n = \frac{1}{n+1}\binom{2n}{n}$ be the $n$-th Catalan number, counting, for example, the number of (rooted) triangulations of the $(n+2)$-gon. Let $P_n$ be the number of three-connected planar ...
1 vote
1 answer
173 views

Who introduced the concept of beyond planar graphs?

The concept of planar graphs seems to be standard (I'm also not sure who first used this term), and recently, beyond planar graphs attract a lot of interest in the field of graph drawing. I know that ...
0 votes
0 answers
81 views

Is there is a constant $c$ such that toroidal graphs are minor-$c$-colorable?

A toroidal graph is a graph that can be embedded on a torus. In other words, the graph's vertices can be placed on a torus such that no edges cross. A minor of graph G is a graph obtained from G by ...
0 votes
3 answers
133 views

Even regular planar graphs without 2-cycles

Related to another question I asked, some questions came up, the most important is the following: Are there any 4-regular planar graphs without 2-cycles + 3-cycles? Could someone draw an example if ...
5 votes
1 answer
119 views

Sufficient condition for a Hamilton cycle $C$ in a planar triangulation $G$ s.t. every triangle in $G$ has an edge in $C$

Let $G$ be a $k$-connected planar triangulation ($k\geq 4$) and let $C$ be a Hamilton cycle of $G$. Then: Which conditions would be sufficient to assure that every triangle of $G$ has at least one ...
3 votes
0 answers
98 views

Number of planar bipartite graphs

How many planar bipartite graphs are there with $m$ vertices of one color and $n$ vertices of the other color? How many non-isomorphic classes exist?
2 votes
1 answer
170 views

Is there an algorithm to generate non-isomorphic Halin graphs?

A Halin graph is a graph constructed by embedding a tree with no vertex of degree two in the plane and then adding a cycle to join the tree’s leaves. We found a list of the number of Halin graphs ...
3 votes
0 answers
136 views

Is there a more intuitive proof that a 1-planar graph with minimum degree 7 contains a $K_4$?

In the following paper, Hudák Dávid, and Tomáš Madaras give the following Theorem 1.1. Hudák, Dávid, and Tomáš Madaras. "On local properties of 1-planar graphs with high minimum degree." ...
2 votes
1 answer
138 views

Two ears polygon in a maximal planar hamiltonian graph

Given a maximal planar graph (+6vertices) without separating triangles. Then it can have many Hamilton cycles°. Such a cycle divides the graph into two triangulated polygons. Is it always possible to ...
0 votes
0 answers
35 views

Arbitrarily high degree planar covers?

All the graphs I want to discuss are finite, simple, and connected. A graph $G_1$ covers another graph $G_2$ if there is a surjective map $\pi : V(G_1) \to V(G_2)$ that sends edges to edges and such ...
3 votes
1 answer
159 views

Planar graphs - more or less

A graph is planar if it can be drawn on the plane in such a way that its edges do not cross each other. A graph is $k$-planar if it can be drawn on the plane in such a way that each of its edges is ...
4 votes
1 answer
205 views

Is there any study on the bounds on the number of even cycles for planar bipartite graphs?

In 1979, Hakimi and Schmeichel [1] initiated such a study by determining the maximum number of triangles and 4-cycles possible in an $n$-vertex planar graph (see also [2] for a small correction). [1] ...
10 votes
2 answers
601 views

Method to draw 3-connected planar graph on a sphere

The Tutte embedding is a way to create a "nice" drawing of a 3-connected planar graph in the plane, after having chosen an outer face. Is there a similar method to draw such a graph on a sphere? ...
3 votes
1 answer
360 views

Is there a way to generate all 5-connected 5-regular planar graphs?

My question was partly inspired by the question linked below. There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....? I see a wonderful construction of Adam P. Goucher,...
36 votes
21 answers
6k views

Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
3 votes
0 answers
166 views

Known bounds of the maximum cut of planar graphs

The well-known max cut problem asks for a largest cut of a graph $G$. A cut of maximal size clearly corresponds to a bipartite subgraph of maximal size. After my inquiry, in planar graphs, the maximum-...
2 votes
0 answers
91 views

Blind construction of planar graph with additive spanning tree count

Suppose we have two planar graphs $G_1$ and $G_2$ with number of spanning tree count $P_1$ and $P_2$ respectively then there is an easy construction which gives a planar graph with spanning tree count ...
37 votes
2 answers
2k views

A conjecture on planar graphs

I don't know the following is a known result, but it would be very useful to me in my research if it were true. Conjecture: Let $G$ be a planar graph. The sum $$ \sum_{\{x,y\} \in E(G)}{\min(\deg(x),\...
2 votes
1 answer
113 views

Completing a tree to a 2-connected outerplanar graph

Let $T$ be a given (finite) tree. Question 1: Is it always possible to add edges to $T$ to obtain a $2$-connected outerplanar supergraph $G$? Question 2: If the answer to Question #1 is negative, can ...
0 votes
0 answers
233 views

I don’t understand the two ISOMORPHISM embedding definitions of planar graph in plantri software

The plantri (see http://users.cecs.anu.edu.au/~bdm/plantri/) is a program that generates certain types of graphs that are imbedded on the sphere. Exactly one member of each isomorphism class is output....
11 votes
1 answer
866 views

Is the divisibility graph of the proper divisors of n more often planar than not?

Define the divisibility graph of a set of positive integers as the graph whose vertices are the integers, two of which are joined by an edge if one divides the other. For all N, is it true that ...
6 votes
1 answer
566 views

Does every $4$-connected nonplanar graph contain a $K_5$-minor?

By Kuratowski's theorem, every nonplanar graph contains a (topological) minor of $K_5$ or $K_{3,3}$. But I observed that every time I construct a $4$-connected nonplanar graph, it always contains not ...
2 votes
0 answers
106 views

Decomposing a planar graph

Thomassen proved that the vertex set of every planar graph can be decomposed into two sets inducing a 1-degenerate graph and a 2-degenerate graph, respectively (C. Thomassen, Decomposing a planar ...
4 votes
1 answer
553 views

Product of vertex degrees of an edge in a planar graph

Let $G$ be a planar graph, which we may assume to be a triangulation, with vertex set $V$ and edge set $E$. Suppose the minimum vertex degree is at least 3, and suppose any two distinct edges share at ...
5 votes
1 answer
187 views

An inequality on the number of vertex colorings of planar graphs

Conjecture: Let $G$ be a simple maximal planar graph, and let $P(G,4)$ be the number of proper vertex colorings of $G$ with four colors. Let $v$ be a vertex of $G$ with degree ${\rm deg}(v)=5$, and ...
1 vote
1 answer
298 views

Confused about the definition of convex drawing of plane graph

When I looked up the definition of convex drawing of planar graph, my confusion mainly focused on the outer face. The following definition of convex drawing is from Wikipedia. In graph drawing, a ...
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 ...
8 votes
0 answers
404 views

Parity of oriented rooted trees

Suppose we have a planar graf with vertices $v_o, \ldots, v_n$, where $n$ is even such that if we checkerboard-color regions in the complement, then the black regions are $n$ (non-degenerated) ...
1 vote
0 answers
52 views

Mac Lane-like condition for intrinsically linked graphs?

If any embedding of your graph in 3-space has two cycles that are linked, then your graph is intrinsically linked (such as the Petersen graph). These graphs generalise non-planar graphs since for ...