Deciding whether graph \(G\) has page number one is in NC

DOI10.1016/0020-0190(92)90247-SzbMath0764.68052OpenAlexW2023008617MaRDI QIDQ1195855

Shigeru Masuyama, Shozo Naito

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

zbMATH Keywords

forbidden subgraphparallel graph algorithmclass NCpage number onepolylog time algorithm

Mathematics Subject Classification ID

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