Comparability graphs and intersection graphs

DOI10.1016/0012-365X(83)90019-5zbMath0502.05050WikidataQ29394678 ScholiaQ29394678MaRDI QIDQ1172652

Martin Charles Golumbic, Jorge Urrutia, Doron Rotem

Publication date: 1983

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

intersection graphcomparability graphpermutation diagramf-diagramfunction graphminimal lense cover

Mathematics Subject Classification ID

Partial orders, general (06A06) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph theory (05C99)

Related Items (58)

Intersection graphs of L-shapes and segments in the plane ⋮ Maximum weight independent sets and cliques in intersection graphs of filaments ⋮ On the structure of certain intersection graphs ⋮ Angle orders, regular n-gon orders and the crossing number ⋮ Double-threshold permutation graphs ⋮ Trapezoid graphs and their coloring ⋮ Vertex deletion into bipartite permutation graphs ⋮ Collision-free routing problem with restricted L-path ⋮ Novel evolutionary models and applications to sequence alignment problems ⋮ Algorithmic aspects of intersection graphs and representation hypergraphs ⋮ New insights on \(\mathbf{GA}\)-\(\mathbf H\) reduced graphs ⋮ On Strict (Outer-)Confluent Graphs ⋮ String graphs. I: The number of critical nonstring graphs is infinite ⋮ Solving a Multigroup Mixed-Integer Programming-Based Constrained Discrimination Model ⋮ Recognizing simple-triangle graphs by restricted 2-chain subgraph cover ⋮ On polygon numbers of circle graphs and distance hereditary graphs ⋮ Complete edge-colored permutation graphs ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Coloring \(K_{k}\)-free intersection graphs of geometric objects in the plane ⋮ Maximum max-k-clique subgraphs in cactus subtree graphs ⋮ Algorithms and complexity of sandwich problems in graphs (extended abstract) ⋮ String graphs have the Erdős-Hajnal property ⋮ On strict (outer-)confluent graphs ⋮ Coloring Hasse diagrams and disjointness graphs of curves ⋮ On String Graph Limits and the Structure of a Typical String Graph ⋮ String graphs and incomparability graphs ⋮ Induced matchings in intersection graphs. ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On graphs associated to sets of rankings ⋮ 3D-interval-filament graphs ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ Weakly transitive orientations, Hasse diagrams and string graphs ⋮ Line-distortion, bandwidth and path-length of a graph ⋮ Thresholds for classes of intersection graphs ⋮ Towards a comprehensive theory of conflict-tolerance graphs ⋮ A bipartite strengthening of the crossing Lemma ⋮ Counting maximal independent sets in directed path graphs ⋮ Vertex deletion into bipartite permutation graphs ⋮ An algorithmic analysis of the Honey-Bee game ⋮ Maximum weight induced multicliques and complete multipartite subgraphs in directed path overlap graphs ⋮ On-line approach to off-line coloring problems on graphs with geometric representations ⋮ Interval \(k\)-graphs and orders ⋮ On the computational complexity of vertex integrity and component order connectivity ⋮ A Bipartite Strengthening of the Crossing Lemma ⋮ Posets and VPG graphs ⋮ Finding a maximum induced matching in weakly chordal graphs ⋮ Bounds on the bend number of split and cocomparability graphs ⋮ Algorithms on Subtree Filament Graphs ⋮ Path Partitions, Cycle Covers and Integer Decomposition ⋮ A bipartite analogue of Dilworth's theorem for multiple partial orders ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ The graphs with maximum induced matching and maximum matching the same size ⋮ Tolerance graphs ⋮ Interval graphs and related topics ⋮ Independent packings in structured graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Comparing series of rankings with ties by using complex networks: an analysis of the Spanish stock market (IBEX-35 index)

Cites Work

• Intersection graphs of curves in the plane
• The complexity of comparability graph recognition and coloring
• The Complexity of the Partial Order Dimension Problem
• The Dimension of a Comparability Graph
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Partial orders of dimension 2
• Permutation Graphs and Transitive Graphs
• A Characterization of Comparability Graphs and of Interval Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Comparability graphs and intersection graphs