Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. I: Theory

DOI10.7155/JGAA.00425MaRDI QIDQ2985115zbMATH OpenOpenAlexFDO

Authors Francisco J. Soulignac

Publication date 16 May 2017

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

minimal modelunit interval graphunit circular-arc graphs

Mathematics Subject Classification ID

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

Recommendations

• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. II: Algorithms
• Unit Circular-Arc Graph Representations and Feasible Circulations
• Polynomial time recognition of unit circular-arc graphs
• Optimal circular arc representations: Properties, recognition, and construction
• Bounded representations of interval and proper interval graphs

Cites work

• scientific article; zbMATH DE number 5556718 (Why is no real title available?)
• scientific article; zbMATH DE number 1554938 (Why is no real title available?)
• scientific article; zbMATH DE number 2100931 (Why is no real title available?)
• scientific article; zbMATH DE number 3342041 (Why is no real title available?)
• Bounded discrete representations of interval orders
• Bounded representations of interval and proper interval graphs
• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. II: Algorithms
• Certifying LexBFS Recognition Algorithms for Proper Interval Graphs and Proper Interval Bigraphs
• Certifying algorithms
• Certifying algorithms for recognizing proper circular-arc graphs and unit circular-arc graphs
• Contact representations of planar graphs: extending a partial representation is hard
• Extending partial representations of circle graphs
• Extending partial representations of function graphs and permutation graphs
• Fully dynamic recognition of proper circular-arc graphs
• Gene clusters as intersections of powers of paths
• Interval graphs: canonical representations in logspace
• Interval routing schemes
• Introduction to algorithms.
• Minimal representation of a semiorder
• On properties of unit interval graphs with a perceptual motivation
• On the concept of the scale
• On the structure of local tournaments
• On unit interval graphs with integer endpoints
• Polynomial time recognition of unit circular-arc graphs
• Powers of cycles, powers of paths, and distance graphs
• Proof of a conjecture of Goodman
• Scheduling of a Smart Antenna: Capacitated Coloring of Unit Circular-Arc Graphs
• Short models for unit interval graphs
• Simple linear time recognition of unit interval graphs
• Simultaneous PQ-ordering with applications to constrained embedding problems
• Solving the canonical representation and star system problems for proper circular-arc graphs in logspace
• Structure theorems for some circular-arc graphs
• Synthetic description of a semiorder
• The Roberts characterization of proper and unit interval graphs
• The representation polyhedron of a semiorder.
• Uniformization of linear arrays
• Unit Circular-Arc Graph Representations and Feasible Circulations

Cited in

(5)

• Bounded, minimal, and short representations of unit interval and unit circular-arc graphs. II: Algorithms
• On the classes of interval graphs of limited nesting and count of lengths
• Unit Circular-Arc Graph Representations and Feasible Circulations
• Recognition and characterization of unit interval graphs with integer endpoints
• Minimal obstructions for partial representations of interval graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2985115)