Deciding whether graph \(G\) has page number one is in NC
From MaRDI portal
Publication:1195855
DOI10.1016/0020-0190(92)90247-SzbMath0764.68052OpenAlexW2023008617MaRDI QIDQ1195855
Publication date: 4 January 1993
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(92)90247-s
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)
Cites Work
- Unnamed Item
- Embedding planar graphs in four pages
- The book thickness of a graph
- Parallel concepts in graph theory
- A linear algorithm for the domination number of a series-parallel graph
- Topology of series-parallel networks
- Efficient parallel algorithms for series parallel graphs
- Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design
- A simple parallel tree contraction algorithm
- Dividing a Graph into Triconnected Components