Suppose I start with a directed chain graph of length $n$:
And then I add $k$ edges, with a restriction that the result is a planar DAG:
Is there a name for this graph family?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Is $k$ at most constant or arbitrary? Can edges added to the bottom-side or only the top-side? $\endgroup$– pcpthmCommented Feb 18, 2022 at 0:29
-
$\begingroup$ edges can be added to any side, the only restriction on $n$ and $k$ is that the result is a planar DAG $\endgroup$– Yaroslav BulatovCommented Feb 18, 2022 at 0:30
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Your graph class coincides with the class of Hamiltonian planar DAGs. See [1] for the undirected version of the equivalence. See also [2] for an account of the directed version.
Proof sketch: given a directed Hamiltonian path, the vertices can be moved continuously to a straight line so the planar embedding is preserved.
The underlying undirected graphs are called book thickness 2, 2-page or 2-stack. This class is equivalent to the subhamiltonian graphs.
- [1]: Frank Bernhart and Paul C Kainen. "The book thickness of a graph." Journal of Combinatorial Theory Series B 27.3 (1979).
- [2]: Binucci Carla et al. "Upward book embeddings of st-graphs." arXiv preprint arXiv:1903.07966 (2019).
