Tractabilities and intractabilities on geometric intersection graphs
type: Item
instance of: scholarly article
title: Tractabilities and intractabilities on geometric intersection graphs
zbMATH Open document ID: 1461.05148
author: Ryuhei Uehara
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: A graph is said to be an intersection graph if there is a set of objects such that each vertex corresponds to an object and two vertices are adjacent if and only if the corresponding objects have a nonempty intersection. There are several natural graph classes that have geometric intersection representations. The geometric representations sometimes help to prove tractability/intractability of problems on graph classes. In this paper, we show some results proved by using geometric representations.
Mathematics Subject Classification ID: 05C62
zbMATH DE Number: 7042151
zbMATH Keywords: bandwidth
zbMATH Keywords: chain graphs
zbMATH Keywords: graph isomorphism
zbMATH Keywords: Hamiltonian path problem
zbMATH Keywords: interval graphs
zbMATH Keywords: threshold graphs
zbMATH Keywords: unit grid intersection graphs
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6010060
OpenAlex ID: W1987721329
cites work: Algorithmic graph theory and perfect graphs
cites work: Efficient graph representations
cites work: Interval graphs and interval orders
cites work: Topics in Intersection Graph Theory
cites work: Simple Geometrical Intersection Graphs
cites work: Bandwidth of Bipartite Permutation Graphs
cites work: A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
cites work: The bandwidth problem for graphs and matrices—a survey
cites work: Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
cites work: Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
cites work: The NP-completeness of the bandwidth minimization problem
cites work: Q4198056
cites work: The Bandwidth Minimization Problem for Caterpillars with Hair Length 3 is NP-Complete
cites work: Q2766686
cites work: Bandwidth of Convex Bipartite Graphs and Related Graphs
cites work: Q2721963
cites work: Exact and approximate bandwidth
cites work: Even Faster Exact Bandwidth
cites work: Bandwidth and distortion revisited
cites work: Bandwidth Minimization: An approximation algorithm for caterpillars
cites work: Approximating the Bandwidth for Asteroidal Triple-Free Graphs
cites work: Improved bandwidth approximation for trees and chordal graphs
cites work: Bandwidth of chain graphs
cites work: Bandwidth and topological bandwidth of graphs with few \(P_4\)'s
cites work: Computing the Bandwidth of Interval Graphs
cites work: On finding the minimum bandwidth of interval graphs
cites work: An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
cites work: Bandwidth of bipartite permutation graphs in polynomial time
cites work: Finding the minimum bandwidth of an interval graph
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism
cites work: Q5463359
cites work: Linear structure of bipartite permutation graphs and the longest path problem
cites work: Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
cites work: Finding Hamiltonian circuits in interval graphs
cites work: HAMILTONian circuits in chordal bipartite graphs
cites work: Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
cites work: $O(M\cdot N)$ Algorithms for the Recognition and Isomorphism Problems on Circular-Arc Graphs
cites work: Q5747380
cites work: Q5588432
cites work: A short proof that `proper = unit'
cites work: Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
cites work: ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
cites work: Random Generation and Enumeration of Bipartite Permutation Graphs
cites work: Graph Classes: A Survey
cites work: Recognizing interval digraphs and interval bigraphs in polynomial time
cites work: Interval bigraphs and circular arc graphs
cites work: Algorithms and Computation
cites work: On testing isomorphism of permutation graphs
cites work: The Isomorphism Problem For Directed Path Graphs and For Rooted Directed Path Graphs
cites work: A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs
cites work: Q4057549
cites work: The NP-completeness of the Hamiltonian cycle problem in planar digraphs with degree bound two
cites work: Q4503944
DOI: 10.3390/A6010060
Recommended article: The complexity of dominating set in geometric intersection graphs
Recommended article: Approximation Algorithms for Geometric Intersection Graphs
Recommended article: Polynomial-Time Approximation Schemes for Geometric Intersection Graphs
Recommended article: Contraction-Bidimensionality of Geometric Intersection Graphs
Recommended article: Intersection dimension and graph invariants

Tractabilities and intractabilities on geometric intersection graphs (Recommended article)
Recommended article: Refining the hierarchies of classes of geometric intersection graphs
Similarity Score: 0.88808465
Recommender Run: Recommender Run 2

Tractabilities and intractabilities on geometric intersection graphs (Recommended article)
Recommended article: Refining the hierarchies of classes of geometric intersection graphs
Similarity Score: 0.88808465
Recommender Run: Recommender Run 2

Tractabilities and intractabilities on geometric intersection graphs (Recommended article)
Recommended article: On the structure of certain intersection graphs
Similarity Score: 0.88437396
Recommender Run: Recommender Run 2

Tractabilities and intractabilities on geometric intersection graphs (Recommended article)
Recommended article: The Dominating Set Problem in Geometric Intersection Graphs
Similarity Score: 0.88426995
Recommender Run: Recommender Run 2

Tractabilities and intractabilities on geometric intersection graphs (Recommended article)
Recommended article: Q4589014
Similarity Score: 0.8834409
Recommender Run: Recommender Run 2