Intersection graphs of curves in the plane
From MaRDI portal
Publication:1234300
DOI10.1016/0095-8956(76)90022-8zbMath0348.05113OpenAlexW2068075837MaRDI QIDQ1234300
Publication date: 1976
Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0095-8956(76)90022-8
Related Items
Disjointness graphs of segments in the space ⋮ A special planar satisfiability problem and a consequence of its NP- completeness ⋮ On the complexity of finite subgraphs of the curve graph ⋮ Decidability of string graphs ⋮ A left-first search algorithm for planar graphs ⋮ On dominating set of some subclasses of string graphs ⋮ Planar graphs have 1-string representations ⋮ Cops and robbers on intersection graphs ⋮ Embedding ray intersection graphs and global curve simplification ⋮ Simultaneous dominance representation of multiple posets ⋮ Max point-tolerance graphs ⋮ Collision-free routing problem with restricted L-path ⋮ String graphs. II: Recognizing string graphs is NP-hard ⋮ On intersection representations of co-planar graphs ⋮ String graphs. I: The number of critical nonstring graphs is infinite ⋮ String graphs requiring exponential representations ⋮ The maximal clique and colourability of curve contact graphs ⋮ Turán-type results for partial orders and intersection graphs of convex sets ⋮ Intersection Graphs of Rays and Grounded Segments ⋮ Characterising circular-arc contact \(B_0\)-VPG graphs ⋮ Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete ⋮ Separability, boxicity, and partial orders ⋮ Proper colorability of segment intersection graphs ⋮ Optimal packing and covering in the plane are NP-complete ⋮ On strict (outer-)confluent graphs ⋮ Coloring Hasse diagrams and disjointness graphs of curves ⋮ Complexity of representation of graphs by set systems ⋮ On String Graph Limits and the Structure of a Typical String Graph ⋮ String graphs and incomparability graphs ⋮ Comparability graphs and intersection graphs ⋮ On grid intersection graphs ⋮ Representations of graphs and networks (coding, layouts and embeddings) ⋮ On the speed of algebraically defined graph classes ⋮ An algorithm for the maximum weight independent set problem on outerstring graphs ⋮ Thresholds for classes of intersection graphs ⋮ The max clique problem in classes of string-graphs ⋮ Conflict-free coloring of string graphs ⋮ Crossing patterns of segments ⋮ Using graph concepts to assess the feasibility of a sequenced air traffic flow with low conflict rate ⋮ Disjoint edges in complete topological graphs ⋮ Unnamed Item ⋮ Classes and recognition of curve contact graphs ⋮ On some special classes of contact \(B_0\)-VPG graphs ⋮ On the Complexity of Planar Covering of Small Graphs ⋮ String graphs of k-bend paths on a grid ⋮ Outerstring Graphs are $\chi$-Bounded ⋮ Crossing patterns of semi-algebraic sets ⋮ Topological queries in spatial databases ⋮ Irrepresentability by multiple intersection, or why the interval number is unbounded
Cites Work