Short Models for Unit Interval Graphs

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

zbMATH Keywords

graph theory; proper interval graphs; unit interval graphs; algorithms and data structures; efficient representation

Mathematics Subject Classification ID

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