Extending partial representations of circle graphs in near-linear time

DOI10.1007/s00453-024-01216-5MaRDI QIDQ6582371

Peter Stumpf, Guido Brückner, Ignaz Rutter

Publication date: 2 August 2024

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

recognitiongeometric intersection graphscircle graphssimultaneous representation

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Practical and efficient circle graph recognition
• Practical and efficient split decomposition via graph-labelled trees
• Extending partial representations of proper and unit interval graphs
• Circle graphs and monadic second-order logic
• Reducing prime graphs and recognizing circle graphs
• Extending partial representations of trapezoid graphs
• Extending simple drawings
• Extending partial representations of interval graphs
• Extending Partial Representations of Function Graphs and Permutation Graphs
• Decomposition of Directed Graphs
• Recognition of Circle Graphs
• $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
• Testing Planarity of Partially Embedded Graphs
• Extending partial representations of circle graphs
• ON EXTENDING A PARTIAL STRAIGHT-LINE DRAWING
• Transitiv orientierbare Graphen
• Circle graph isomorphism in almost linear time
• Partial and simultaneous transitive orientations via modular decompositions

This page was built for publication: Extending partial representations of circle graphs in near-linear time