Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms

DOI10.7155/jgaa.00426zbMath1361.05090OpenAlexW4246050455MaRDI QIDQ2985116

Francisco J. Soulignac

Publication date: 16 May 2017

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.7155/jgaa.00426

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (4)

Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ Minimal obstructions for partial representations of interval graphs ⋮ On the classes of interval graphs of limited nesting and count of lengths ⋮ Extending partial representations of proper and unit interval graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On unit interval graphs with integer endpoints
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Certifying algorithms
• Extending partial representations of proper and unit interval graphs
• Powers of cycles, powers of paths, and distance graphs
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Synthetic description of a semiorder
• Minimal representation of a semiorder
• Structure theorems for some circular-arc graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory
• Uniformization of linear arrays
• Unit Circular-Arc Graph Representations and Feasible Circulations
• Stability in circular arc graphs
• Polynomial time recognition of unit circular-arc graphs

This page was built for publication: Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter II: algorithms