Short Models for Unit Interval Graphs
From MaRDI portal
Publication:2840545
DOI10.1016/j.endm.2009.11.041zbMath1268.05138MaRDI QIDQ2840545
Min Chih Lin, Francisco J. Soulignac, Jayme Luiz Szwarcfiter
Publication date: 19 July 2013
Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.endm.2009.11.041
graph theory; proper interval graphs; unit interval graphs; algorithms and data structures; efficient representation
05C62: Graph representations (geometric and intersection representations, etc.)
Related Items
On unit interval graphs with integer endpoints, On the non-unit count of interval graphs, On sum coloring and sum multi-coloring for restricted families of graphs, Normal Helly circular-arc graphs and its subclasses, Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory
Cites Work
- Powers of cycles, powers of paths, and distance graphs
- Simple linear time recognition of unit interval graphs
- A short proof that `proper = unit'
- Efficient graph representations
- A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
- The Roberts characterization of proper and unit interval graphs
- Unit Circular-Arc Graph Representations and Feasible Circulations
- Unnamed Item