All Questions
7 questions
1
vote
1
answer
173
views
Who introduced the concept of beyond planar graphs?
The concept of planar graphs seems to be standard (I'm also not sure who first used this term), and recently, beyond planar graphs attract a lot of interest in the field of graph drawing. I know that ...
- 1,851
6
votes
3
answers
526
views
Enumerating all inequivalent planar embeddings of a planar graph
Graph $G$ can be embedded (or has an embedding) in the space if $G$ can be drawn in the space if $G$ can be drawn in such a way that no two edges cross except at an end-vertex in common. A Graph $G$ ...
- 1,851
3
votes
0
answers
136
views
Is there a more intuitive proof that a 1-planar graph with minimum degree 7 contains a $K_4$?
In the following paper, Hudák Dávid, and Tomáš Madaras give the following Theorem 1.1.
Hudák, Dávid, and Tomáš Madaras. "On local properties of 1-planar graphs with high minimum degree." ...
- 1,851
7
votes
2
answers
252
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,190
5
votes
2
answers
553
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 ...
- 1,034
5
votes
1
answer
479
views
Can all crossings in a graph be moved to one point?
Consider a graph $G$ with at least two unavoidable crossings, say, the disjoint union of two copies of $K_5$. Can such a graph always be drawn so that there is only one singular point (where all ...
- 4,829
7
votes
2
answers
1k
views
Planar layouts of bipartite graphs
Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar.
It would be very convenient if there was a ...
- 4,462