Trapezoid graphs and generalizations, geometry and algorithms

DOI10.1016/S0166-218X(96)00013-3zbMath0877.68093OpenAlexW2047570770MaRDI QIDQ678864

Rudolf Müller, Stefan Felsner, Lorenz Wernisch

Publication date: 27 November 1997

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

Full work available at URL: http://www.elsevier.com/locate/dam

zbMATH Keywords

chromatic numbertrapezoid graphscircle trapezoid graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Combinatorics of partially ordered sets (06A07) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items

MINIMUM WEIGHT FEEDBACK VERTEX SETS IN CIRCLE n-GON GRAPHS AND CIRCLE TRAPEZOID GRAPHS ⋮ On the computational complexity of 2-interval pattern matching problems ⋮ Maximum weight independent sets and cliques in intersection graphs of filaments ⋮ Approximation algorithms for maximum weight k-coverings of graphs by packings ⋮ Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems ⋮ Measuring the vulnerability for classes of intersection graphs ⋮ On Strict (Outer-)Confluent Graphs ⋮ Efficient algorithms for the minimum connected domination on trapezoid graphs ⋮ Efficient algorithm for the vertex connectivity of trapezoid graphs ⋮ Algorithms for \(\mathcal{GA}\mathrm{-}\mathcal H\) reduced graphs ⋮ Donation center location problem ⋮ Powers of geometric intersection graphs and dispersion algorithms ⋮ The recognition of triangle graphs ⋮ On the vertex ranking problem for trapezoid, circular-arc and other graphs ⋮ Approximation of RNA multiple structural alignment ⋮ No-Wait Scheduling for Locks ⋮ Approximating the 2-interval pattern problem ⋮ Extracting constrained 2-interval subsets in 2-interval sets ⋮ New results on induced matchings ⋮ 3D-interval-filament graphs ⋮ Unit and proper tube orders ⋮ An intersection model for multitolerance graphs: efficient algorithms and hierarchy ⋮ On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs ⋮ A characterization of interval orders with semiorder dimension two ⋮ A 2-approximation for the preceding-and-crossing structured 2-interval pattern problem ⋮ Improved algorithms for largest cardinality 2-interval pattern problem ⋮ The hub number of co-comparability graphs ⋮ Dominating the complements of bounded tolerance graphs and the complements of trapezoid graphs ⋮ Grundy dominating sequences on \(X\)-join product ⋮ Succinct navigational oracles for families of intersection graphs on a circle ⋮ Efficient maximum matching algorithms for trapezoid graphs ⋮ Algorithms for maximum weight induced paths ⋮ Efficient Algorithms for Maximum Induced Matching Problem in Permutation and Trapezoid Graphs ⋮ AN IMPROVED PARALLEL ALGORITHM FOR A GEOMETRIC MATCHING PROBLEM WITH APPLICATION TO TRAPEZOID GRAPHS

Cites Work

• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Trapezoid graphs and their coloring
• On computing the length of longest increasing subsequences
• Preserving order in a forest in less than logarithmic time and linear space
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Unnamed Item
• Unnamed Item
• Unnamed Item