Testing Full Outer-2-planarity in Linear Time

DOI10.1007/978-3-662-53174-7_29MaRDI QIDQ2827826zbMATH OpenOpenAlexFDO

Authors Seok-Hee Hong, Hiroshi Nagamochi

Publication date 21 October 2016

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-53174-7_29

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10)

Recommendations

• A linear-time algorithm for testing full outer-2-planarity
• A linear-time algorithm for testing outer-1-planarity
• A linear-time algorithm for testing outer-1-planarity
• Fully-dynamic planarity testing in polylogarithmic time
• scientific article; zbMATH DE number 1377359
• On the linearity of testing planarity of graphs
• Testing planarity of geometric automorphisms in linear time
• scientific article; zbMATH DE number 1500509
• The complexity of planarity testing
• Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system
• A linear-time algorithm for testing outer-1-planarity
• Algorithms for graphs embeddable with few crossings per edge
• Drawing graphs with right angle crossings
• Fan-planar graphs: combinatorial properties and complexity results
• Fáry's theorem for 1-planar graphs
• Graphs drawn with few crossings per edge
• On the maximum number of edges in topological graphs with no four pairwise crossing edges
• On the recognition of fan-planar and maximal outer-fan-planar graphs
• On-Line Planarity Testing
• Quasi-planar graphs have a linear number of edges
• Recognizing outer 1-planar graphs in linear time
• Rectilinear drawings of graphs
• Testing Full Outer-2-planarity in Linear Time
• The number of edges in k-quasi-planar graphs
• The straight-line RAC drawing problem is NP-hard

Cited in

(14)

• A direct linear-time planarity test for unflippable modules
• scientific article; zbMATH DE number 7651192 (Why is no real title available?)
• scientific article; zbMATH DE number 1377359 (Why is no real title available?)
• Fully-dynamic planarity testing in polylogarithmic time
• Rectilinear Planarity Testing of Plane Series-Parallel Graphs in Linear Time
• A heuristic approach towards drawings of graphs with high crossing resolution
• A linear-time algorithm for testing full outer-2-planarity
• Testing Full Outer-2-planarity in Linear Time
• Gap-Planar Graphs
• Beyond outerplanarity
• On the density of non-simple 3-planar graphs
• Gap-planar graphs
• On RAC drawings of graphs with one bend per edge
• \(k\)-planar graphs

This page was built for publication: Testing Full Outer-2-planarity in Linear Time

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