Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [planar-graphs]

The tag has no usage guidance.

3
votes
1answer
210 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\...
2
votes
0answers
33 views

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 ...
3
votes
0answers
36 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
1answer
201 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
0answers
64 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 ...
7
votes
0answers
69 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
2answers
206 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
1answer
76 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
0answers
104 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
3answers
454 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
1answer
305 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
1answer
72 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 ...
32
votes
2answers
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
1answer
100 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
1answer
236 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
2answers
493 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 ...
3
votes
1answer
368 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 ...
6
votes
1answer
378 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 ...
14
votes
1answer
1k 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 ...