# Questions tagged [planar-graphs]

The tag has no usage guidance.

33 questions
Filter by
Sorted by
Tagged with
54 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 ...
110 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 ...
42 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 ...
124 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 ...
65 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 ...
232 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 ...
66 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 ...
181 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 ...
50 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 ...
72 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 ...
167 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? ...
118 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!)...
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 ...