String graphs requiring exponential representations

DOI10.1016/0095-8956(91)90050-TzbMath0675.05059MaRDI QIDQ1121918

Jan Kratochvíl, Ji{ří} Matoušek

Publication date: 1991

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

intersection graphcurves

Mathematics Subject Classification ID

Graph theory (05C99)

Related Items (37)

CPG graphs: some structural and hardness results ⋮ Decidability of string graphs ⋮ Untangling two systems of noncrossing curves ⋮ Hanani--Tutte and Hierarchical Partial Planarity ⋮ On intersection representations of co-planar graphs ⋮ The maximal clique and colourability of curve contact graphs ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Almost all string graphs are intersection graphs of plane convex sets ⋮ Folding and Spiralling: The Word View ⋮ String graphs have the Erdős-Hajnal property ⋮ Simple realizability of complete abstract topological graphs in P ⋮ String graphs and incomparability graphs ⋮ Spatial reasoning with \(\mathcal{RCC} 8\) and connectedness constraints in Euclidean spaces ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ Thresholds for classes of intersection graphs ⋮ Spiraling and folding: the word view ⋮ Conflict-free coloring of string graphs ⋮ Crossing patterns of segments ⋮ Optimality program in segment and string graphs ⋮ Recognizing string graphs in NP ⋮ General lower bounds for the minor crossing number of graphs ⋮ Crossing Numbers and Parameterized Complexity ⋮ The Complexity of Several Realizability Problems for Abstract Topological Graphs ⋮ Posets and VPG graphs ⋮ Drawing Simultaneously Embedded Graphs with Few Bends ⋮ Subexponential-time algorithms for finding large induced sparse subgraphs ⋮ Refining the hierarchies of classes of geometric intersection graphs ⋮ Unnamed Item ⋮ Subexponential algorithms for variants of the homomorphism problem in string graphs ⋮ Classes and recognition of curve contact graphs ⋮ Maximum Independent Set in 2-Direction Outersegment Graphs ⋮ Separators in region intersection graphs ⋮ Bounds on the bend number of split and cocomparability graphs ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Segment representations with small resolution ⋮ Almost all string graphs are intersection graphs of plane convex sets

Cites Work

• String graphs. II: Recognizing string graphs is NP-hard
• Intersection graphs of curves in the plane
• Energy, central charge, and the BPS bound for \(1+1\)-dimensional supersymmetric solitons
• Topology of Thin Film RC Circuits

This page was built for publication: String graphs requiring exponential representations