Representation of a finite graph by a set of intervals on the real line

DOI10.4064/fm-51-1-45-64zbMath0105.17501OpenAlexW1517921658MaRDI QIDQ3290351

Jan Ch. Boland, C. Gerrit Lekkerkerker

Publication date: 1962

Published in: Fundamenta Mathematicae (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/213681

zbMATH Keywords

topology

Related Items

Minimal triangulations of graphs: a survey, Graphs with induced-saturation number zero, Neighborhood perfect graphs, Castelnuovo-Mumford regularity under reduction processes on graphs and hypergraphs, Balanced independent and dominating sets on colored interval graphs, Structural parameterizations for boxicity, On models of directed path graphs non rooted directed path graphs, Vertex ranking of asteroidal triple-free graphs, Bandwidth of chain graphs, Finding the minimum bandwidth of an interval graph, Combining overlap and containment for gene assembly in ciliates, On the problem of how to represent a graph taking into account an additional structure, On unit interval graphs with integer endpoints, Strictly interval graphs: characterization and linear time recognition, Largest chordal and interval subgraphs faster than \(2^n\), Posets with interval upper bound graphs, Fuzzy intersection graphs, A note on path domination, Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection, Max point-tolerance graphs, Random interval graphs, The structure of bi-arc trees, A characterization of interval catch digraphs, Simplicial decompositions of graphs: A survey of applications, End vertices in interval graphs, Tree representations of graphs, On dimensional properties of graphs, Tree loop graphs, Recognizing graphs without asteroidal triples, Reconstruction of interval graphs, On CCE graphs of doubly partial orders, A characterization of Robert's inequality for boxicity, Detecting induced minors in AT-free graphs, Recognition and characterization of chronological interval digraphs, Asteroidal quadruples in non rooted path graphs, New characterizations of proper interval bigraphs, Reduced clique graphs of chordal graphs, Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms, Extremal values of the interval number of a graph. II, Linear-time recognition of Helly circular-arc models and graphs, Extremal values of the interval number of a graph, II, On minimal augmentation of a graph to obtain an interval graph, An evolution of interval graphs, Computing feasible toolpaths for 5-axis machines, Computing role assignments of proper interval graphs in polynomial time, The asymptotic probability that a random graph is a unit interval graph, indifference graph, or proper interval graph, An optimal greedy heuristic to color interval graphs, Faster parameterized algorithms for \textsc{Minimum Fill-in}, Characterizing paths graphs on bounded degree trees by minimal forbidden induced subgraphs, On grid intersection graphs, Some properties of edge intersection graphs of single-bend paths on a grid, Short-chorded and perfect graphs, Representations of graphs and networks (coding, layouts and embeddings), Intersection properties of graphs, Boxicity of leaf powers, Minimal obstructions for partial representations of interval graphs, On the non-unit count of interval graphs, A linear time algorithm to compute a dominating path in an AT-free graph, Norbert Wiener on the theory of measurement (1914, 1915, 1921), Strict chordal and strict split digraphs, A new characterization of proper interval graphs, Fixed-parameter complexity of minimum profile problems, Interval competition graphs of symmetric digraphs, Two-step graphs of trees, End-vertices of LBFS of (AT-free) bigraphs, A structural characterization for certifying Robinsonian matrices, Separator orders in interval, cocomparability, and AT-free graphs, On end-vertices of lexicographic breadth first searches, Fast minimal triangulation algorithm using minimum degree criterion, On listing, sampling, and counting the chordal graphs with edge constraints, d-collapsing and nerves of families of convex sets, A recognition algorithm for the intersection graphs of directed paths in directed trees, Bigraphs/digraphs of Ferrers dimension 2 and asteroidal triple of edges, On distance-3 matchings and induced matchings, Comparability graphs and a new matroid, Information storage and retrieval - mathematical foundations. II: Combinatorial problems, Information storage and retrieval systems: Mathematical foundations, Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Interval hypergraphs and D-interval hypergraphs, Computing the boxicity of a graph by covering its complement by cointerval graphs, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, A Turan type problem for interval graphs, The circular dimension of a graph, Representing triangulated graphs in stars, Counting clique trees and computing perfect elimination schemes in parallel, Two minimal forbidden subgraphs for double competition graphs of posets of dimension at most two, A Ramsey-type theorem and its application to relatives of Helly's theorem, Representation theorems for graphs whose vertex set is partially ordered, On the stab number of rectangle intersection graphs, A lower bound for the interval number of a graph, Some remarks on interval graphs, Some aspects of perfect elimination orderings in chordal graphs, Interval line graphs, Tolerance graphs, Interval graphs and interval orders, Finding Hamiltonian circuits in interval graphs, Homogeneously representable interval graphs, Interval graphs and maps of DNA, An integer programming approach for the 2-schemes strip cutting problem with a sequencing constraint, The structure of obstructions to treewidth and pathwidth, Periodic assignment and graph colouring, Optimal patchings for consecutive ones matrices, Compatibility between interval structures and partial orderings, Optimal greedy algorithms for indifference graphs, Optimal decomposition by clique separators, Characterizations of two classes of digraphs, Representing a concept lattice by a graph, Chordal probe graphs, On the \(m\)-clique free interval subgraphs polytope: polyhedral analysis and applications, Tolerance intersection graphs of degree bounded subtrees of a tree with constant tolerance 2, On the intersection graphs of orthogonal line segments in the plane: characterizations of some subclasses of chordal graphs, Faster FPT algorithms for deletion to pairs of graph classes, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Uniquely orderable interval graphs, Double-threshold permutation graphs, Vertex deletion into bipartite permutation graphs, A graph theoretic approach to similarity relations, The one-dimensional Euclidean domain: finitely many obstructions are not enough, Structural properties of Toeplitz graphs, Graph extremities defined by search algorithms, Complexity of paired domination in AT-free and planar graphs, Characterizations and algorithmic applications of chordal graph embeddings, Hamiltonian paths, unit-interval complexes, and determinantal facet ideals, Triangulating graphs without asteroidal triples, Robinsonian matrices: recognition challenges, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, The existence of a pure Nash equilibrium in the two-player competitive diffusion game on graphs having chordality, Subpath acyclic digraphs, Recognizing interval digraphs and interval bigraphs in polynomial time, Extending partial representations of interval graphs, The maximal clique and colourability of curve contact graphs, Toric chordality, A width parameter useful for chordal and co-comparability graphs, Chronological rectangle digraphs which are two-terminal series-parallel, Characterizing interval graphs which are probe unit interval graphs, Proper circular arc graphs as intersection graphs of paths on a grid, The niche graphs of bipartite tournaments, Separability generalizes Dirac's theorem, Matching and multidimensional matching in chordal and strongly chordal graphs, 2-role assignments on triangulated graphs., On linear and circular structure of (claw, net)-free graphs, Interval degree and bandwidth of a graph, Classes of perfect graphs, Normal Helly circular-arc graphs and its subclasses, Proper interval vertex deletion, A short note on the complexity of computing strong pathbreadth, Induced matchings in asteroidal triple-free graphs, Interval numbers of powers of block graphs, Hereditary dominating pair graphs, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, Which distance-hereditary graphs are cover-incomparability graphs?, Induced matchings in intersection graphs., Structural results on circular-arc graphs and circle graphs: a survey and the main open problems, On asteroidal sets in chordal graphs, A note on the geodetic number and the Steiner number of AT-free graphs, Polynomial treedepth bounds in linear colorings, A characterization of the single-crossing domain, Reconstruction and verification of chordal graphs with a distance oracle, Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs, Random geometric complexes and graphs on Riemannian manifolds in the thermodynamic limit, A certifying and dynamic algorithm for the recognition of proper circular-arc graphs, On the classes of interval graphs of limited nesting and count of lengths, Convex and isometric domination of (weak) dominating pair graphs, Recognition and characterization of unit interval graphs with integer endpoints, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Tree decomposition and discrete optimization problems: a survey, Towards a comprehensive theory of conflict-tolerance graphs, Toll convexity, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, On the structure of (\(P_{5}\),\,gem)-free graphs, Constant tolerance intersection graphs of subtrees of a tree, On the interval completion of chordal graphs, Representation characterizations of chordal bipartite graphs, Fast algorithms for identifying maximal common connected sets of interval graphs, On the Steiner, geodetic and hull numbers of graphs, NP-completeness results for edge modification problems, Dichotomy for tree-structured trigraph list homomorphism problems, Characterization of the graphs with boxicity \(\leq 2\), Dyadic representations of graphs, A characterization of 2-tree probe interval graphs, On the \(e\)-positivity of \((claw, 2K_2)\)-free graphs, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Junction trees of general graphs, Chordality, \(d\)-collapsibility, and componentwise linear ideals, Induced matchings, Induced disjoint paths in AT-free graphs, On superperfection of edge intersection graphs of paths, Small one-dimensional Euclidean preference profiles, Phylogeny numbers, Classes and recognition of curve contact graphs, An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs, Optimal cell flipping to minimize channel density in VLSI design and pseudo-Boolean optimization, AT-free graphs: Linear bounds for the oriented diameter, Classes of graphs with \(e\)-positive chromatic symmetric function, On stable cutsets in graphs, The forbidden subgraph characterization of directed vertex graphs, Completeness for intersection classes, Fully dynamic recognition of proper circular-arc graphs, Recognizing geometric intersection graphs stabbed by a line, Maximum Semiorders in Interval Orders, Extremal Values of the Interval Number of a Graph, Monotonic Representations of Outerplanar Graphs as Edge Intersection Graphs of Paths on a Grid, Unnamed Item, Distance approximating spanning trees, Characterizing directed path graphs by forbidden asteroids, Unnamed Item, Computing a dominating pair in an asteroidal triple-free graph in linear time, Connected domination and steiner set on asteroidal triple-free graphs, Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs, Characterizing circular-arc graphs, Reconstruction of Interval Graphs, Independent sets in asteroidal triple-free graphs, Query-competitive sorting with uncertainty, Incidence matrices with the consecutive 1’s property, Tverberg-type theorems with altered intersection patterns (nerves), Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, Minimal Obstructions for Partial Representations of Interval Graphs, A Characterization of Mixed Unit Interval Graphs, Computing list homomorphisms in geometric intersection graphs, A Model for Birdwatching and other Chronological Sampling Activities, Two new characterizations of path graphs, The diameter of AT‐free graphs, Polynomial Kernel for Interval Vertex Deletion, Partial Characterizations of Circular-Arc Graphs, Clique trees of chordal graphs: leafage and 3-asteroidals, Erdős–Pósa property of obstructions to interval graphs, Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes, Minimum Eccentricity Shortest Path Problem: An Approximation Algorithm and Relation with the k-Laminarity Problem, On Local Structures of Cubicity 2 Graphs, Axiomatic characterization of the toll walk function of some graph classes, Round-competitive algorithms for uncertainty problems with parallel queries, Asteroidal triple-free graphs, On characterizing proper max-point-tolerance graphs, Path eccentricity of graphs, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Unnamed Item, Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs, Unnamed Item, Online coloring of short intervals, Strong Cocomparability Graphs and Slash-Free Orderings of Matrices, On the enumeration of interval graphs, Counting Interval Graphs, Unnamed Item, Bipartite Analogues of Comparability and Cocomparability Graphs, Min-Orderable Digraphs, The caterpillar-packing polytope, Treewidth and pathwidth of permutation graphs, Two-Player Competitive Diffusion Game: Graph Classes and the Existence of a Nash Equilibrium, Computing Role Assignments of Proper Interval Graphs in Polynomial Time, The caterpillar-packing polytope, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, Total domination in interval graphs, Hypergraphs and intervals, Asteroidal triples of moplexes, Tree-decompositions of small pathwidth, Vertex deletion into bipartite permutation graphs, Intersection graphs of non-crossing paths, The graphs of semirings, On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs, Diameter determination on restricted graph families, Proper Interval Vertex Deletion, Tree-decompositions of small pathwidth, Enumeration and maximum number of maximal irredundant sets for chordal graphs, Two strikes against perfect phylogeny, Higher chordality: From graphs to complexes, Complexes of graphs with bounded independence number, On rectangle intersection graphs with stab number at most two, Query minimization under stochastic uncertainty, On the power of BFS to determine a graph's diameter, Intransitive indifference with unequal indifference intervals, On nontransitive indifference, A structure theorem for the consecutive 1's property, Betweenness, orders and interval graphs, Linear-Time Recognition of Probe Interval Graphs, Unnamed Item, Description of some relations on the set of real-line intervals, Bounds for the boxicity of Mycielski graphs, Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut, Partial characterizations of circular-arc graphs, Characterizing path graphs by forbidden induced subgraphs, Asteroids in rooted and directed path graphs, Adjusted Interval Digraphs, Non-separating cliques, asteroidal number and leafage. The minimal 4-asteroidal split graphs, Probe interval and probe unit interval graphs on superclasses of cographs, The Interval Count of a Graph, The intersection graphs of subtrees in trees are exactly the chordal graphs, Facet-inducing inequalities with acyclic supports for the caterpillar-packing polytope, Zdzisław Pawlak, Databases and Rough Sets, A generalization of the theorem of Lekkerkerker and Boland, Lexicographic Orientation Algorithms, d-collapsibility is NP-complete for <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:mi>d</mml:mi><mml:mo>⩾</mml:mo><mml:mn>4</mml:mn></mml:math>, Efficient Local Representations of Graphs, Graph Classes and Forbidden Patterns on Three Vertices, Independent packings in structured graphs, Asteroidal Triple of Edges in Bichordal Graphs: A Complete list, Asteroidal Chromatic Number of a Graph, Helly-type problems, Transitiv orientierbare Graphen