Parameterized Complexity of 1-Planarity
From MaRDI portal
Publication:2842148
DOI10.1007/978-3-642-40104-6_9zbMath1390.68329arXiv1304.5591OpenAlexW1960374579MaRDI QIDQ2842148
David Eppstein, Sergio Cabello, Michael J. Bannister
Publication date: 12 August 2013
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1304.5591
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Outer 1-planar graphs, Recognizing and drawing IC-planar graphs, Recognizing IC-Planar and NIC-Planar Graphs, On quasi-planar graphs: clique-width and logical description, An annotated bibliography on 1-planarity, \(\mathsf{NIC}\)-planar graphs, A note on 1-planar graphs, Track Layout Is Hard, Recognizing optimal 1-planar graphs in linear time, Fixed-parameter algorithms for the weighted max-cut problem on embedded 1-planar graphs, A linear-time algorithm for testing full outer-2-planarity, A linear-time algorithm for testing outer-1-planarity, Re-embedding a 1-plane graph for a straight-line drawing in linear time, Ortho-polygon visibility representations of embedded graphs, Remarks on the joins of 1-planar graphs, Width, depth, and space: tradeoffs between branching and dynamic programming
