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

DOI10.7155/JGAA.00425zbMATH Open1361.05089OpenAlexW2604353676MaRDI QIDQ2985115FDOQ2985115

Authors: 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.00425

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

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)

Cites Work

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

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)