Questions tagged [planar-graphs]

graphs that can be embedded into the plane, i.e. that can be drawn without crossings between the lines representing edges.

Filter by
Sorted by
Tagged with
0 votes
0 answers
19 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 ...
L.C. Zhang's user avatar
  • 1,605
0 votes
0 answers
23 views

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

Suppose $G$ is a graph with $m=|E(G)|$ edges and $n=|V(G)|$ vertices. Suppose $sim(G)$, the simplification of $G$ contains $ m' >> 3n $ edges. Call the set of edges corresponding to an edge $uv$...
Hao S's user avatar
  • 181
3 votes
0 answers
95 views

Positive boolean satisfiability problem : finding minimal solutions

Consider, over a finite set of boolean variables $X$, a Boolean system in CNF (conjunctive normal form) whose clauses only contain non-negated literals. For every assignment of the variables which ...
Christopher-Lloyd Simon's user avatar
1 vote
1 answer
78 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 ...
L.C. Zhang's user avatar
  • 1,605
6 votes
1 answer
273 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?
Xin Zhang's user avatar
  • 1,130
7 votes
1 answer
281 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 ...
L.C. Zhang's user avatar
  • 1,605
2 votes
0 answers
62 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 ...
L.C. Zhang's user avatar
  • 1,605
2 votes
0 answers
229 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 ...
Martin Rubey's user avatar
  • 5,533
1 vote
1 answer
161 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 ...
L.C. Zhang's user avatar
  • 1,605
3 votes
1 answer
124 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 ...
Lorenzo Pompili's user avatar
0 votes
0 answers
78 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 ...
Xin Zhang's user avatar
  • 1,130
5 votes
2 answers
286 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$ ...
L.C. Zhang's user avatar
  • 1,605
0 votes
3 answers
123 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 ...
Kregnach's user avatar
5 votes
1 answer
104 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 ...
Jose Antonio Martin H's user avatar
3 votes
0 answers
88 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?
Turbo's user avatar
  • 13.7k
2 votes
1 answer
157 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 ...
L.C. Zhang's user avatar
  • 1,605
0 votes
0 answers
27 views

What is known about "overlapping" models/minors of graphs

Suppose we are given a graph $G$ from a graph class of sublinear treewidth and connected subgraphs $G_1,G_2,..,G_l$ of $G$ such that each $G_i$ intersects (shares a node with) constant many other $G_j$...
Hao S's user avatar
  • 181
3 votes
0 answers
129 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." ...
L.C. Zhang's user avatar
  • 1,605
2 votes
1 answer
128 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 ...
P.Labarque's user avatar
0 votes
0 answers
34 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 ...
Sprotte's user avatar
  • 1,065
3 votes
1 answer
154 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 ...
Matthieu Latapy's user avatar
4 votes
1 answer
156 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] ...
L.C. Zhang's user avatar
  • 1,605
3 votes
1 answer
279 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,...
L.C. Zhang's user avatar
  • 1,605
6 votes
2 answers
605 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 ...
W. Paul Liu's user avatar
3 votes
0 answers
121 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-...
L.C. Zhang's user avatar
  • 1,605
2 votes
0 answers
90 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 ...
Turbo's user avatar
  • 13.7k
2 votes
1 answer
98 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 ...
Felix Goldberg's user avatar
0 votes
0 answers
202 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....
L.C. Zhang's user avatar
  • 1,605
1 vote
0 answers
65 views

On perfect matchings on planar graphs - is there a linear time deterministic algorithm?

The slides here provide a way to get a pfaffian orientation from Minimum Spanning Tree. MST can be found in linear time if graph is planar and weights are $1$ and the slides give a linear time ...
Turbo's user avatar
  • 13.7k
11 votes
1 answer
851 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 ...
Bernardo Recamán Santos's user avatar
6 votes
1 answer
457 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 ...
okw1124's user avatar
  • 331
4 votes
0 answers
131 views

Chromatic number of rectangle tilings

Suppose we have a region of the plane tiled by finitely many rectangles. We want to color the rectangles so that two rectangles have different colors if they share a part of an edge or if they share ...
Adam Chalcraft's user avatar
2 votes
0 answers
100 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 ...
jack's user avatar
  • 2,929
5 votes
1 answer
184 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 ...
Martin Weidner's user avatar
4 votes
1 answer
528 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 ...
Grant Lakeland's user avatar
3 votes
1 answer
479 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 ...
L.C. Zhang's user avatar
  • 1,605
1 vote
1 answer
246 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 ...
L.C. Zhang's user avatar
  • 1,605
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 ...
ben macintosh's user avatar
5 votes
2 answers
297 views

Distribution over Penrose Tilings?

The set of possible kit-and-dart Penrose tilings is uncountably infinite. It would be very helpful to have some natural probability distribution $\mu$ over this set; such a distribution would allow ...
Bill Bradley's user avatar
  • 3,809
1 vote
1 answer
150 views

Can Tutte embedding be guaranteed that each face is convex?

In graph drawing and geometric graph theory, a Tutte embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a ...
L.C. Zhang's user avatar
  • 1,605
0 votes
1 answer
184 views

Is graph's planar embedding unique if each block of one planar graph is 3-connected?

A planar graph is one which has a plane embedding. Two drawings are topologically isomorphic if one can be continuously deformed into the other. If we wrap a drawing onto a sphere, and then off again, ...
L.C. Zhang's user avatar
  • 1,605
1 vote
0 answers
64 views

Why are trivalent/cubic graphs 'generic' in surfaces?

I've seen some statements that trivalent graphs in a surface are 'generic'. See for example the Wiki entry on cubic graphs. I'm wondering how this could be rephrased. Here are some (somewhat imprecise)...
Joe's user avatar
  • 535
8 votes
0 answers
401 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) ...
user avatar
7 votes
1 answer
1k 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 ...
rimu's user avatar
  • 749
0 votes
0 answers
120 views

is there an example in planar graph that using probabilistic methods

The probabilistic method is a technique for proving the existence of an object with certain properties by showing that a random object chosen from an appropriate probability distribution has the ...
L.C. Zhang's user avatar
  • 1,605
5 votes
0 answers
117 views

Equitable 4-colorings of planar triangulations

In an equitable coloring of a graph $G$, the number of vertices in each color class differ by at most $1$. For example, left below is not an equitable coloring, while the right graph is equitably ...
Joseph O'Rourke's user avatar
2 votes
1 answer
184 views

Two from cubic subgraph hardness

The Problem For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3. The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...
prohibited graph minor's user avatar
3 votes
2 answers
264 views

Planar graph of high valence

A classic result in graph theory tells us that any planar graph must have at least one vertex with valence no bigger than 5. On the other hand, there exist examples of planar graphs that are 5-regular ...
Daps's user avatar
  • 540
7 votes
2 answers
240 views

There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?

Is there any characterization on the set of integers $n$ such that there is a 3-connected 5-regular simple $n$-vertex planar graph?
Xin Zhang's user avatar
  • 1,130
1 vote
0 answers
318 views

What is the standard definition of dual of disconnected planar graph when underlying graph derives 'product structure' over connected graphs?

Dual graph of a plane graph has a standard definition https://en.wikipedia.org/wiki/Dual_graph and an edgeless graph on $n$ vertices is planar. What is the standard dual graph of such a graph? Update ...
VS.'s user avatar
  • 1,816