# 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.

45
questions

**5**

votes

**1**answer

142 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 ...

**1**

vote

**1**answer

91 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 ...

**0**

votes

**1**answer

58 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, ...

**1**

vote

**0**answers

48 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)...

**4**

votes

**0**answers

255 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) ...

**4**

votes

**0**answers

314 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 ...

**0**

votes

**0**answers

105 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 ...

**5**

votes

**0**answers

81 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 ...

**2**

votes

**0**answers

98 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 ...

**3**

votes

**2**answers

192 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 ...

**5**

votes

**2**answers

139 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?

**1**

vote

**0**answers

131 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 ...

**2**

votes

**1**answer

171 views

### Implementation of Koebe–Andreev–Thurston circle packing?

The circle packing theorem (Koebe–Andreev–Thurston theorem) claims for a planar graph, we can pack disjoint circles, such that: the circles correspond to vertices and the disks are tangent if the ...

**2**

votes

**0**answers

46 views

### Planarity of a subgraph

Given a complete symmetric graph $G(V,E)$ with real-valued edgeweights and assume that every induced $k_4$ that is induced by a quadruplet from $v$'s vertices has a unique perfect matching of maximal ...

**12**

votes

**0**answers

145 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 ...

**0**

votes

**0**answers

110 views

### crossing number and thickness of a simple graph $G$

Crossing number$($cr$)$: The crossing number of a simple graph is the minimum number of crossings that can occur when this graph is drawn in the plane where no three arcs representing edges are ...

**4**

votes

**0**answers

242 views

### Reference for results about planar graphs

A colleague and I are writing a paper in which we need to make use of some basic facts about planar graphs. I would strongly prefer to simply give references for the results if possible, because the ...

**4**

votes

**0**answers

77 views

### Can the vertices of a planar graph of min degree 3 be covered with edges of average weight ( sum of degrees) at most 14?

Consider a planar graph where every vertex is incident to at least 3 edges, and assign to each edge a weight equal to the sum of the degrees of its endpoints.
If not, what is the smallest n so that ...

**2**

votes

**0**answers

184 views

### The drawn diagonals divide the $N\times N$ board into $K$ regions. For each $N$, determine the smallest and the largest possible values of $K$

Let $N$ be a positive integer. In each of the $N^2$ unit squares of an $N\times N$ board, one of the two diagonals is drawn. The drawn diagonals divide the $N\times N$ board into $K$ regions. For each ...

**1**

vote

**0**answers

59 views

### Planar graphs with perfect matching count in linear time?

We can find Pfaffian orientation and take determinant to compute permanent in $O(n^\omega)$ time where $\omega$ is exponent of matrix multiplication.
We know that permanent of $O(n)$ vertex planar ...

**2**

votes

**0**answers

98 views

### Graphs determined by monohedral, edge-to-edge tilings of the plane

Let $\cal T$ be a monohedral, edge-to-edge tiling of the plane, with prototile $T$ a simple polygon, and with one edge $e^*$ of $T$ distinguished. Associate a graph $G=G_{\cal T}$ with $\cal T$ as ...

**8**

votes

**1**answer

292 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? ...

**2**

votes

**2**answers

127 views

### Does any long path in a planar graph contain one of O(n) k-tuple of vertices?

My question is a bit related to both the container method and shallow cell complexity.
Let's start with that the number of length $\ell$ paths (where $\ell$ denotes the number of vertices of the path!)...

**4**

votes

**2**answers

352 views

### “Locally Nonplanar” graph

A 2-connected $3$-connected graph $G$ is "Almost Planar" Locally Nonplanar if it has a a $2$-connected spanning subgraph $H$ and an embedding in the plane such that $H$ is planar in this embedding and ...

**3**

votes

**1**answer

289 views

### Minimum planar bipartite graph to cover all perfect matching count

Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...

**5**

votes

**0**answers

80 views

+50

### Volume interpretation of number of perfect matchings in bipartite planar graphs

Permanent of biadjacency of bipartite graphs is the number of perfect matchings. In the case of planar graphs we can obtain an orientation with sign changes and get away with computing the determinant ...

**4**

votes

**0**answers

85 views

### Reference on generalization of plane graph duality between bonds and simple cycles

Let $G$ be a plane graph, and $G^*$ its dual. Among the $k$ partitions of the nodes of $G$, I'll call the connected k-partitions those such that each block of nodes of the partition induces a ...

**10**

votes

**1**answer

251 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 ...

**3**

votes

**0**answers

164 views

### Reconstructing plane graphs from degree- and face-sequences

Let $G$ be a plane $3$-connected graph; so it partitions the plane
into regions bounded by faces.
Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$,
and $\mathrm{deg}_f$ be the sequence of ...

**9**

votes

**0**answers

96 views

### Partitioning the vertices of a graph into induced trees

I am looking for previous work regarding graphs whose vertices can be assigned colours (not necessarily a proper colouring) in such a way that each colour class induces a tree.
In particular I am ...

**9**

votes

**2**answers

246 views

### Graph planarization via rewiring

Let $G$ be a nonplanar graph (undirected) of $n$ nodes and $e$ edges, with
$e \le 3n-6$.
Define a rewiring move as replacing edge $(a,b)$ with edge $(a,c)$.
The result must be a simple graph (no loops,...

**3**

votes

**1**answer

103 views

### A question regarding the all pair shortest paths in weighted planar graphs

What is the time complexity of the fastest known algorithm for the all-pair shortest paths in planar graphs?

**1**

vote

**0**answers

157 views

### Smallest planar graph with two non-homoemorphic plane embeddings?

Apologies for asking a question which probably has a well-known answer:
What is the smallest (not necessarily simple) planar graph with two non-homeomorphic embeddings into the plane?
I am ...

**4**

votes

**3**answers

480 views

### Does every finite bridgeless cubic planar simple undirected graph admit a 2-factorization with at most two components each of which has even order?

Consider simple bridgeless cubic planar graphs.
Does each such graph admit a 2-factorization with $\leq 2$ components each of which has even order?
If not, does anyone know of an counterexample?
...

**0**

votes

**1**answer

338 views

### How to prove that there does not exist any plane isotopy from the logarithmic spiral onto the real line? [closed]

Questions.
EDIT: readers please note that while this question arose in research, the OP was so hung-up on a question concerning infinite planar graphs that a strong a-forteriori-reason, kindly ...

**1**

vote

**1**answer

81 views

### Cholesky factorization of planar graphs

Suppose the sparsity pattern of $A \in \mathbb{R}^{N \times N}$ is a planar graph. Can I use this to bound the complexity of solving
$$
Ax = b
$$
?
In particular, I was hoping to use the planar ...

**35**

votes

**2**answers

1k 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),...

**1**

vote

**1**answer

136 views

### When is an ordering of edges in a graph a planar embedding?

Is there a criterion which decides whether a given rotation system for a graph determines a planar embedding? That is, a lemma of the form:
A graph G = (V, E) is planar if and only if there exists ...

**5**

votes

**1**answer

290 views

### In how many ways can a given planar graph be mapped into the plane?

I feel sure that this question must have been addressed in the literature, but I can't seem to find it - I may be looking in the wrong place.
A graph is planar if it can be drawn on the plane such ...

**14**

votes

**2**answers

778 views

### Is there easy proof for triangle-free two-coloring of planar graphs?

By merging two-two color classes, the Four Color Theorem implies that every planar graph can be two-colored such that each color class induces a triangle-free graph.
Is there a simpler proof for this ...

**4**

votes

**1**answer

398 views

### How non-planar is the Math Genealogy Project graph? [closed]

The Mathematics Genealogy Project keeps an online database of information on as many mathematicians as they can get records for, focusing especially on advisor-student relationships. In this way, they ...

**9**

votes

**2**answers

469 views

### Do planar graphs have an acyclic two-coloring?

A graph has an acyclic two-coloring if its vertices can be colored with two colors such that each color class spans a forest.
Does every planar graph have an acyclic two-coloring?
An affirmative ...

**1**

vote

**0**answers

101 views

### Determine sub-polygon from line segments with known member connectivity

Test Polygon:
Consider the following polygon as attached. Let the known parameter be as follows:
•Member to member connectivity, i.e. it is known that A – B, X – E, F – B, etc. for all the members.
•...

**14**

votes

**1**answer

2k views

### Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest
distance to vertices in $G$, e.g., in the graph below, that radius is $4$:
Define the ...

**1**

vote

**0**answers

206 views

### A connection between nonplanar complete graphs and the alternating groups?

I didn't get any response on MSE so I though I'd give this a try here (my question on MSE).
I went to an undergrad's senior honors thesis presentation a while ago. She was discussing crossing numbers ...