Angles of arc-polygons and lombardi drawings of cacti

DOI10.1016/J.COMGEO.2023.101982zbMATH Open1514.05115arXiv2107.03615OpenAlexW3182139134MaRDI QIDQ6103170FDOQ6103170

Authors: David Eppstein, Daniel Frishberg, Martha Carolina Osegueda 

Publication date: 26 June 2023

Published in: Computational Geometry (Search for Journal in Brave)

Abstract: We characterize the triples of interior angles that are possible in non-self-crossing triangles with circular-arc sides, and we prove that a given cyclic sequence of angles can be realized by a non-self-crossing polygon with circular-arc sides whenever all angles are at most pi. As a consequence of these results, we prove that every cactus has a planar Lombardi drawing (a drawing with edges depicted as circular arcs, meeting at equal angles at each vertex) for its natural embedding in which every cycle of the cactus is a face of the drawing. However, there exist planar embeddings of cacti that do not have planar Lombardi drawings.

Full work available at URL: https://arxiv.org/abs/2107.03615

Recommendations

• Planar Lombardi Drawings for Subcubic Graphs
• Bipartite and series-parallel graphs without planar Lombardi drawings
• Lombardi drawings of graphs

zbMATH Keywords

cactus graphsgraph drawingarc-polygons

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph representations (geometric and intersection representations, etc.) (05C62)

Cites Work

• A Better Approximation Algorithm for Finding Planar Subgraphs
• On the Geometry of Piecewise Circular Curves
• On the usability of Lombardi graph drawings
• Some results on greedy embeddings in metric spaces
• Mitered offsets and skeletons for circular arc polygons
• Lombardi drawings of graphs
• Approximating smooth planar curves by arc splines
• On the Number of Husimi Trees
• Drawing trees with perfect angular resolution and polynomial area
• Force-directed Lombardi-style graph drawing
• A Möbius-invariant power diagram and its applications to soap bubbles and planar Lombardi drawing
• Universal Point Sets for Drawing Planar Graphs with Circular Arcs
• Approximation by polygons and polyhedra
• Drawing Graphs with Few Arcs
• An improved force-directed graph layout algorithm based on aesthetic criteria
• Force-directed graph drawing using social gravity and scaling
• Arc diagrams, flip distances, and Hamiltonian triangulations
• How to draw the minimum cuts of a planar graph
• Bipartite and series-parallel graphs without planar Lombardi drawings
• Drawing planar graphs with circular arcs
• Computational and structural advantages of circular boundary representation
• Lombardi drawings of knots and links
• Triangulations with Circular Arcs
• Fixed-Location Circular Arc Drawing of Planar Graphs

This page was built for publication: Angles of arc-polygons and lombardi drawings of cacti

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