# 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
Filter by
Sorted by
Tagged with
1answer
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 ...
1answer
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 ...
1answer
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, ...
0answers
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)...
0answers
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) ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
2answers
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 ...
2answers
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?
0answers
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 ...
1answer
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
0answers
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 ...
1answer
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? ...
2answers
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!)...
2answers
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 ...
1answer
289 views

0answers
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 ...