Editing Circle graph (section)

==Applications==
Circle graphs arise in [[VLSI]] [[Physical design (electronics)|physical design]] as an abstract representation for a special case for [[wire routing]], known as "two-terminal [[switchbox routing]]". In this case the [[routing area]] is a rectangle, all nets are two-terminal, and the terminals are placed on the perimeter of the rectangle. It is easily seen that the intersection graph of these nets is a circle graph.<ref>Naveed Sherwani, "Algorithms for VLSI Physical Design Automation"</ref>  Among the goals of wire routing step is to ensure that different nets stay electrically disconnected, and  their potential intersecting parts must be [[integrated circuit layout|laid out]] in different conducting layers. Therefore circle graphs capture various aspects of this routing problem.

Colorings of circle graphs may also be used to find [[book embedding]]s of arbitrary graphs: if the vertices of a given graph ''G'' are arranged on a circle, with the edges of ''G'' forming chords of the circle, then the intersection graph of these chords is a circle graph and colorings of this circle graph are equivalent to book embeddings that respect the given circular layout. In this equivalence, the number of colors in the coloring corresponds to the number of pages in the book embedding.{{sfnp|Unger|1988}}