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.

7
votes
0answers
70 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 ...
3
votes
0answers
38 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 ...
3
votes
0answers
65 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 ...
2
votes
0answers
34 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 ...
1
vote
0answers
107 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 ...