Recognizing outer 1-planar graphs in linear time

DOI10.1007/978-3-319-03841-4_10MaRDI QIDQ2867648zbMATH OpenOpenAlexFDO

Authors Christopher Auer, Christian Bachmaier, Andreas Gleißner, Kathrin Hanauer, Daniel Neuwirth, Josef Reislhuber, Franz J. Brandenburg

Publication date 20 December 2013

Published in Graph Drawing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-319-03841-4_10

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Outer 1-planar graphs
• A linear-time algorithm for testing outer-1-planarity
• A linear-time algorithm for testing outer-1-planarity
• Recognizing optimal 1-planar graphs in linear time
• scientific article; zbMATH DE number 4049084

Cited in

(16)

• Recognizing optimal 1-planar graphs in linear time
• A linear-time algorithm for testing full outer-2-planarity
• Linear arboricity of outer-1-planar graphs
• Recognizing and embedding simple optimal 2-planar graphs
• Fan-planarity: properties and complexity
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• Testing Full Outer-2-planarity in Linear Time
• A linear-time algorithm for testing outer-1-planarity
• Outer 1-planar graphs
• A linear-time algorithm for testing outer-1-planarity
• Drawing outer-1-planar graphs revisited
• Incidence coloring of outer-1-planar graphs
• Conflict-free incidence coloring of outer-1-planar graphs
• Bounding the treewidth of outer k-planar graphs via triangulations
• The price of upwardness
• The edge chromatic number of outer-1-planar graphs

This page was built for publication: Recognizing outer 1-planar graphs in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2867648)