Graph embedding: Difference between revisions

Revision as of 12:45, 5 July 2021

Revision as of 09:59, 9 June 2022

Line 32:

Often, an '''embedding''' is regarded as an equivalence class (under homeomorphisms of <math>\Sigma</math>) of representations of the kind just described.

Some authors define a weaker version of the definition of "graph embedding" by omitting the non-intersection condition for edges. In such contexts the stricter definition is described as "non-crossing graph embedding".<ref>{{citation|first1=Naoki|last1=Katoh|first2=Shin-ichi|last2=Tanigawa|title=Computing and Combinatorics, 13th Annual International Conference, COCOON 2007, Banff, Canada, July 16-19, 2007, Proceedings|publisher=Springer-Verlag|series=[[Lecture Notes in Computer Science]]|volume=4598|year=2007|pages=243–253|doi=10.1007/978-3-540-73545-8_25|chapter=Enumerating Constrained Non-crossing Geometric Spanning Trees|isbn=978-3-540-73544-1|citeseerx=10.1.1.483.874}}.</ref>

This article deals only with the strict definition of graph embedding. The weaker definition is discussed in the articles "[[graph drawing]]" and "[[Crossing number (graph theory)|crossing number]]".

Line 58:

The problem of finding the graph genus is [[NP-hard]] (the problem of determining whether an <math>n</math>-vertex graph has genus <math>g</math> is [[NP-complete]]).<ref>{{Citation | last1=Thomassen | first1=Carsten | authorlink = Carsten Thomassen | title=The graph genus problem is NP-complete | year=1989 | journal=Journal of Algorithms | volume=10 | issue = 4 | pages=568–576 | doi = 10.1016/0196-6774(89)90006-0}}</ref>

At the same time, the graph genus problem is [[Fixed-parameter tractability|fixed-parameter tractable]], i.e., [[polynomial time]] algorithms are known to check whether a graph can be embedded into a surface of a given fixed genus as well as to find the embedding.

The first breakthrough in this respect happened in 1979, when algorithms of [[time complexity]]

''O''(''n''^''O''(''g'')) were independently submitted to the Annual [[ACM Symposium on Theory of Computing]]: one by I. Filotti and [[Gary Miller (computer scientist)|G.L. Miller]] and another one by [[John Reif]]. Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.<ref>{{citation|first1=I. S.|last1=Filotti|author2-link=Gary Miller (computer scientist)|first2=Gary L.|last2=Miller|first3=John|last3=Reif|author3-link=John Reif |title=Proc. 11th Annu. ACM Symposium on Theory of Computing|year=1979|pages=27–37|doi=10.1145/800135.804395|chapter=On determining the genus of a graph in O(v O(g)) steps(Preliminary Report)|title-link=Symposium on Theory of Computing}}.</ref> However, [[Wendy Myrvold]] and [[William Lawrence Kocay|William Kocay]] proved in 2011 that the algorithm given by Filotti, Miller and Reif was incorrect.<ref>{{cite journal|last1=Myrvold|first1=Wendy|author1-link=Wendy Myrvold|last2=Kocay|first2=William|author2-link=William Lawrence Kocay|title=Errors in Graph Embedding Algorithms|journal=Journal of Computer and System Sciences|date=March 1, 2011|volume=2|issue=77|page=430–438|doi=10.1016/j.jcss.2010.06.002|doi-access=free}}</ref>

In 1999 it was reported that the fixed-genus case can be solved in time [[linear time|linear]] in the graph size and [[Double exponential function|doubly exponential]] in the genus.<ref>{{Citation | last1=Mohar | first1=Bojan | authorlink = Bojan Mohar | title=A linear time algorithm for embedding graphs in an arbitrary surface | year=1999 | journal=[[SIAM Journal on Discrete Mathematics]] | volume=12 | issue=1 | pages=6–26 | doi = 10.1137/S089548019529248X| citeseerx=10.1.1.97.9588 }}</ref>

==Embeddings of graphs into higher-dimensional spaces==

It is known that any finite graph can be embedded into a three-dimensional space.<ref name="3d-gd"/>

One method for doing this is to place the points on any line in space and to draw the edges as curves each of which lies in a distinct [[halfplane]], with all halfplanes having that line as their common boundary. An embedding like this in which the edges are drawn on halfplanes is called a [[book embedding]] of the graph. This [[metaphor]] comes from imagining that each of the planes where an edge is drawn is like a page of a book. It was observed that in fact several edges may be drawn in the same "page"; the ''book thickness'' of the graph is the minimum number of halfplanes needed for such a drawing.

Alternatively, any finite graph can be drawn with straight-line edges in three dimensions without crossings by placing its vertices in [[general position]] so that no four are coplanar. For instance, this may be achieved by placing the ''i''th vertex at the point (''i'',''i''²,''i''³) of the [[moment curve]].

Line 76:

==Gallery==

<gallery>

File:Petersen-graph.png|thumb|The [[Petersen graph]] and associated map embedded in the projective plane. Opposite points on the circle are identified yielding a closed surface of non-orientable genus 1.

File:Pappus-graph-on-torus.png|The [[Pappus graph]] and associated map embedded in the torus.

File:Klein-map.png|thumb|The degree 7 [[Klein graph]] and associated map embedded in an orientable surface of genus 3.

</gallery>