Noncrossing Subgraphs in Topological Layouts

DOI10.1137/0404022MaRDI QIDQ3357538zbMATH OpenOpenAlexFDO

Authors Jan Kratochvíl, Anna Lubiw, J. Nešetřil

Publication date 1991

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/0404022

zbMATH Keywords

computational complexityNP-completeplanar layouttopological graphstopological layout

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Algorithms and Computation
• Noncrossing subgraphs in the topological graph \(K_{3,3}\)
• Which crossing number is it anyway?
• Crossing Number is NP-Complete
• On rectilinear topological graphs

Cited in

(30)

• The complexity of detecting crossingfree configurations in the plane
• Satisfiability of co-nested formulas
• The complexity of induced minors and related problems
• On the complexity of trial and error for constraint satisfaction problems
• Complete graph drawings up to triangle mutations
• Parameterized analysis and crossing minimization problems
• Simple realizability of complete abstract topological graphs simplified
• Polyline drawings with topological constraints
• Advancements on SEFE and partitioned book embedding problems
• Crossing-constrained hierarchical drawings
• Topological Drawings of Complete Bipartite Graphs
• Plane subgraphs in geometric complement of 2-factor and complete bipartite geometric graph
• Noncrossing subgraphs in the topological graph \(K_{3,3}\)
• On rectilinear topological graphs
• scientific article; zbMATH DE number 6963888 (Why is no real title available?)
• Connecting the dots (with minimum crossings)
• Planar 3-SAT with a clause/variable cycle
• Bad drawings of small complete graphs
• Advances on testing C-planarity of embedded flat clustered graphs
• The Complexity of Several Realizability Problems for Abstract Topological Graphs
• Algorithms and Computation
• The Complexity of Drawing Graphs on Few Lines and Few Planes
• Make a graph singly connected by edge orientations
• Simple realizability of complete abstract topological graphs in P
• An algorithm for the maximum weight independent set problem on outerstring graphs
• Covering complete geometric graphs by monotone paths
• Simple realizability of abstract topological graphs
• Complexity of (p, q)-bipartition of planar and 1-planar graphs
• Configurations with few crossings in topological graphs
• Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs

This page was built for publication: Noncrossing Subgraphs in Topological Layouts

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