Intersection graphs of curves in the plane

From MaRDI portal
Publication:1234300

DOI10.1016/0095-8956(76)90022-8zbMath0348.05113OpenAlexW2068075837MaRDI QIDQ1234300

K. Appert

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 spaceA special planar satisfiability problem and a consequence of its NP- completenessOn the complexity of finite subgraphs of the curve graphDecidability of string graphsA left-first search algorithm for planar graphsOn dominating set of some subclasses of string graphsPlanar graphs have 1-string representationsCops and robbers on intersection graphsEmbedding ray intersection graphs and global curve simplificationSimultaneous dominance representation of multiple posetsMax point-tolerance graphsCollision-free routing problem with restricted L-pathString graphs. II: Recognizing string graphs is NP-hardOn intersection representations of co-planar graphsString graphs. I: The number of critical nonstring graphs is infiniteString graphs requiring exponential representationsThe maximal clique and colourability of curve contact graphsTurán-type results for partial orders and intersection graphs of convex setsIntersection Graphs of Rays and Grounded SegmentsCharacterising circular-arc contact \(B_0\)-VPG graphsRecognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-CompleteSeparability, boxicity, and partial ordersProper colorability of segment intersection graphsOptimal packing and covering in the plane are NP-completeOn strict (outer-)confluent graphsColoring Hasse diagrams and disjointness graphs of curvesComplexity of representation of graphs by set systemsOn String Graph Limits and the Structure of a Typical String GraphString graphs and incomparability graphsComparability graphs and intersection graphsOn grid intersection graphsRepresentations of graphs and networks (coding, layouts and embeddings)On the speed of algebraically defined graph classesAn algorithm for the maximum weight independent set problem on outerstring graphsThresholds for classes of intersection graphsThe max clique problem in classes of string-graphsConflict-free coloring of string graphsCrossing patterns of segmentsUsing graph concepts to assess the feasibility of a sequenced air traffic flow with low conflict rateDisjoint edges in complete topological graphsUnnamed ItemClasses and recognition of curve contact graphsOn some special classes of contact \(B_0\)-VPG graphsOn the Complexity of Planar Covering of Small GraphsString graphs of k-bend paths on a gridOuterstring Graphs are $\chi$-BoundedCrossing patterns of semi-algebraic setsTopological queries in spatial databasesIrrepresentability by multiple intersection, or why the interval number is unbounded



Cites Work