Short Models for Unit Interval Graphs

DOI10.1016/j.endm.2009.11.041zbMath1268.05138OpenAlexW2038728506MaRDI 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 theoryproper interval graphsunit interval graphsalgorithms and data structuresefficient representation

Mathematics Subject Classification ID

Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (5)

On unit interval graphs with integer endpoints ⋮ Normal Helly circular-arc graphs and its subclasses ⋮ Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. Chapter I: theory ⋮ On the non-unit count of interval graphs ⋮ On sum coloring and sum multi-coloring for restricted families of graphs

Cites Work

• Unnamed Item
• 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

This page was built for publication: Short Models for Unit Interval Graphs