Dual circumference and collinear sets

DOI10.1007/s00454-022-00418-4zbMath1506.05145OpenAlexW4289300525WikidataQ114229292 ScholiaQ114229292MaRDI QIDQ2679595

Pat Morin, Vida Dujmović

Publication date: 23 January 2023

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-022-00418-4

zbMATH Keywords

planar graphscircumferenceuntanglingcollinear sets

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• Untangling planar graphs from a specified vertex position-Hard cases
• Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
• Untangling polygons and graphs
• A polynomial bound for untangling geometric planar graphs
• Untangling a planar graph
• Longest cycles in 3-connected cubic graphs
• Triangulating planar graphs while minimizing the maximum degree
• The four-colour theorem
• Circumference of 3-connected cubic graphs
• Untangling a polygon
• Every collinear set in a planar graph is free
• Shortness exponents of families of graphs
• SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs
• Column Planarity and Partial Simultaneous Geometric Embedding
• On Collinear Sets in Straight-Line Drawings
• Longest Cycles in 3-Connected 3-Regular Graphs
• Drawing planar graphs with many collinear vertices
• Universal Point Subsets for Planar Graphs
• Upper Bound Constructions for Untangling Planar Geometric Graphs
• Column planarity and partially-simultaneous geometric embedding
• Trees in Polyhedral Graphs
• On Hamiltonian Circuits
• The Utility of Untangling

This page was built for publication: Dual circumference and collinear sets