String graph

Last updated • 4 min readFrom Wikipedia, The Free Encyclopedia

In graph theory, a string graph is an intersection graph of curves in the plane; each curve is called a "string". Given a graph G, G is a string graph if and only if there exists a set of curves, or strings, such that the graph having a vertex for each curve and an edge for each intersecting pair of curves is isomorphic to G.

Contents

Background

SeymourBenzer  ( 1959 ) described a concept similar to string graphs as they applied to genetic structures. In that context, he also posed the specific case of intersecting intervals on a line, namely the now classical family of interval graphs. Later, Sinden (1966) specified the same idea to electrical networks and printed circuits. The mathematical study of string graphs began with the paper Ehrlich, Even & Tarjan (1976) and through a collaboration between Sinden and Ronald Graham, where the characterization of string graphs eventually came to be posed as an open question at the 5th Hungarian Colloquium on Combinatorics in 1976. [1] However, the recognition of string graphs was eventually proven to be NP-complete, implying that no simple characterization is likely to exist. [2]

Representation of a planar graph as a string graph. Planar string graph.svg
Representation of a planar graph as a string graph.

Every planar graph is a string graph: [3] one may form a string graph representation of an arbitrary plane-embedded graph by drawing a string for each vertex that loops around the vertex and around the midpoint of each adjacent edge, as shown in the figure. For any edge uv of the graph, the strings for u and v cross each other twice near the midpoint of uv, and there are no other crossings, so the pairs of strings that cross represent exactly the adjacent pairs of vertices of the original planar graph. Alternatively, by the circle packing theorem, any planar graph may be represented as a collection of circles, any two of which cross if and only if the corresponding vertices are adjacent; these circles (with a starting and ending point chosen to turn them into open curves) provide a string graph representation of the given planar graph. Chalopin, Gonçalves & Ochem (2007) proved that every planar graph has a string representation in which each pair of strings has at most one crossing point, unlike the representations described above. Scheinerman's conjecture, now proven, is the even stronger statement that every planar graph may be represented by the intersection graph of straight line segments, a very special case of strings.

A subdivision of K5 that is not a string graph. Subdivided K5.svg
A subdivision of K5 that is not a string graph.

If every edge of a given graph G is subdivided, the resulting graph is a string graph if and only if G is planar. In particular, the subdivision of the complete graph K5 shown in the illustration is not a string graph, because K5 is not planar. [3]

Every circle graph, as an intersection graph of line segments (the chords of a circle), is also a string graph. Every chordal graph may be represented as a string graph: chordal graphs are intersection graphs of subtrees of trees, and one may form a string representation of a chordal graph by forming a planar embedding of the corresponding tree and replacing each subtree by a string that traces around the subtree's edges.

The complement graph of every comparability graph is also a string graph. [4]

Other results

Ehrlich, Even & Tarjan (1976) showed computing the chromatic number of string graphs to be NP-hard. Kratochvil (1991a) found that string graphs form an induced minor closed class, but not a minor closed class of graphs.

Every m-edge string graph can be partitioned into two subsets, each a constant fraction the size of the whole graph, by the removal of O(m3/4log1/2m) vertices. It follows that the biclique-free string graphs, string graphs containing no Kt,t subgraph for some constant t, have O(n) edges and more strongly have polynomial expansion. [5]

Notes

  1. Graham (1976).
  2. Kratochvil (1991b) showed string graph recognition to be NP-hard, but was not able to show that it could be solved in NP. After intermediate results by Schaefer & Štefankovič (2001) and Pach & Tóth (2002), Schaefer, Sedgwick & Štefankovič (2003) completed the proof that the problem is NP-complete.
  3. 1 2 Schaefer & Štefankovič (2001) credit this observation to Sinden (1966).
  4. Golumbic, Rotem & Urrutia (1983) and Lovász (1983). See also Fox & Pach (2010).
  5. Fox & Pach (2010); Dvořák & Norin (2016).

Related Research Articles

<span class="mw-page-title-main">Tree decomposition</span> Mapping of a graph into a tree

In graph theory, a tree decomposition is a mapping of a graph into a tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph.

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Perfect graph</span> Graph with tight clique-coloring relation

In graph theory, a perfect graph is a graph in which the chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic number is greater than or equal to the size of the maximum clique, but they can be far apart. A graph is perfect when these numbers are equal, and remain equal after the deletion of arbitrary subsets of vertices.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a chord, which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs: a chordal completion of a graph is typically called a triangulation of that graph.

<span class="mw-page-title-main">Cograph</span> Graph formed by complementation and disjoint union

In graph theory, a cograph, or complement-reducible graph, or P4-free graph, is a graph that can be generated from the single-vertex graph K1 by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K1 and is closed under complementation and disjoint union.

<span class="mw-page-title-main">Scheinerman's conjecture</span> Mathematics theorem

In mathematics, Scheinerman's conjecture, now a theorem, states that every planar graph is the intersection graph of a set of line segments in the plane. This conjecture was formulated by E. R. Scheinerman in his Ph.D. thesis (1984), following earlier results that every planar graph could be represented as the intersection graph of a set of simple curves in the plane. It was proven by Jeremie Chalopin and Daniel Gonçalves.

<span class="mw-page-title-main">Book embedding</span> Graph layout on multiple half-planes

In graph theory, a book embedding is a generalization of planar embedding of a graph to embeddings in a book, a collection of half-planes all having the same line as their boundary. Usually, the vertices of the graph are required to lie on this boundary line, called the spine, and the edges are required to stay within a single half-plane. The book thickness of a graph is the smallest possible number of half-planes for any book embedding of the graph. Book thickness is also called pagenumber, stacknumber or fixed outerthickness. Book embeddings have also been used to define several other graph invariants including the pagewidth and book crossing number.

In graph theory, a clique graph of an undirected graph G is another graph K(G) that represents the structure of cliques in G.

In graph theory, a comparability graph is an undirected graph that connects pairs of elements that are comparable to each other in a partial order. Comparability graphs have also been called transitively orientable graphs, partially orderable graphs, containment graphs, and divisor graphs. An incomparability graph is an undirected graph that connects pairs of elements that are not comparable to each other in a partial order.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Intersection graph</span> Graph representing intersections between given sets

In graph theory, an intersection graph is a graph that represents the pattern of intersections of a family of sets. Any graph can be represented as an intersection graph, but some important special classes of graphs can be defined by the types of sets that are used to form an intersection representation of them.

<span class="mw-page-title-main">Boxicity</span> Smallest dimension where a graph can be represented as an intersection graph of boxes

In graph theory, boxicity is a graph invariant, introduced by Fred S. Roberts in 1969.

Planarity is a 2005 puzzle computer game by John Tantalo, based on a concept by Mary Radcliffe at Western Michigan University. The name comes from the concept of planar graphs in graph theory; these are graphs that can be embedded in the Euclidean plane so that no edges intersect. By Fáry's theorem, if a graph is planar, it can be drawn without crossings so that all of its edges are straight line segments. In the planarity game, the player is presented with a circular layout of a planar graph, with all the vertices placed on a single circle and with many crossings. The goal for the player is to eliminate all of the crossings and construct a straight-line embedding of the graph by moving the vertices one by one into better positions.

<span class="mw-page-title-main">János Pach</span> Hungarian mathematician

János Pach is a mathematician and computer scientist working in the fields of combinatorics and discrete and computational geometry.

In mathematics, the graph structure theorem is a major result in the area of graph theory. The result establishes a deep and fundamental connection between the theory of graph minors and topological embeddings. The theorem is stated in the seventeenth of a series of 23 papers by Neil Robertson and Paul Seymour. Its proof is very long and involved. Kawarabayashi & Mohar (2007) and Lovász (2006) are surveys accessible to nonspecialists, describing the theorem and its consequences.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

<span class="mw-page-title-main">Pancyclic graph</span>

In the mathematical study of graph theory, a pancyclic graph is a directed graph or undirected graph that contains cycles of all possible lengths from three up to the number of vertices in the graph. Pancyclic graphs are a generalization of Hamiltonian graphs, graphs which have a cycle of the maximum possible length.

<span class="mw-page-title-main">Topological graph</span>

In mathematics, a topological graph is a representation of a graph in the plane, where the vertices of the graph are represented by distinct points and the edges by Jordan arcs joining the corresponding pairs of points. The points representing the vertices of a graph and the arcs representing its edges are called the vertices and the edges of the topological graph. It is usually assumed that any two edges of a topological graph cross a finite number of times, no edge passes through a vertex different from its endpoints, and no two edges touch each other. A topological graph is also called a drawing of a graph.

<span class="mw-page-title-main">Ptolemaic graph</span>

In graph theory, a Ptolemaic graph is an undirected graph whose shortest path distances obey Ptolemy's inequality, which in turn was named after the Greek astronomer and mathematician Ptolemy. The Ptolemaic graphs are exactly the graphs that are both chordal and distance-hereditary; they include the block graphs and are a subclass of the perfect graphs.

In graph theory, a class of graphs is said to have few cliques if every member of the class has a polynomial number of maximal cliques. Certain generally NP-hard computational problems are solvable in polynomial time on such classes of graphs, making graphs with few cliques of interest in computational graph theory, network analysis, and other branches of applied mathematics. Informally, a family of graphs has few cliques if the graphs do not have a large number of large clusters.

References