Circle Graphs
system:sage


<link type="text/css" rel="stylesheet" href="graphics-test.css" /><div class="maketitle">
                                                                                         
                                                                                         
                                                                                         
                                                                                         

<h2 class="titleHead">Circle Graphs</h2>
<div class="author"><span class="cmr-12">Robert Beezer</span></div><br/>
<div class="date"><span class="cmr-12">February 20, 2010</span></div>
   </div><h3 class="sectionHead"><span class="titlemark">1   </span> <a id="x1-10001"/>Circle graphs</h3><p class="noindent">A graph is <span class="cmti-10">circle graph </span>if its vertices can be represented as chords of a circle such that two chords interesct if and
only if corresponding vertices form an edge in the graph. As an example of an external link, see the <a href="http://en.wikipedia.org/wiki/Circle_graph">Wikipedia
article</a> on circle graphs. Which is where the tikz code below was lifted from.
</p><h3 class="sectionHead"><span class="titlemark">2   </span> <a id="x1-20002"/>Incorporating tikz graphics</h3><p class="noindent">This is a minor rearrangement of the code for the graphics mentioned in the Wikipedia article. The e&#64256;ect is to place
the two &#64257;gures side-by-side in a centered table. The &#8220;scale&#8221; has been reduced to 2 from an original value of 4.
</p><div class="center">
<!--l. 49--><p class="noindent">
</p>
                                                                                         
                                                                                         
<div class="tabular"> <table cellpadding="0" cellspacing="0" class="tabular" id="TBL-2"><colgroup id="TBL-2-1g"><col id="TBL-2-1"/><col id="TBL-2-2"/></colgroup><tr id="TBL-2-1-" style="vertical-align:baseline;"><td class="td11" id="TBL-2-1-1" style="text-align:center; white-space:nowrap;"><object data="graphics-test-1.svg" height="146.27711 " type="image/svg+xml" width="169.03821 "><p>SVG-Viewer needed.</p></object></td><td class="td11" id="TBL-2-1-2" style="text-align:center; white-space:nowrap;"><object data="graphics-test-2.svg" height="154.8807 " type="image/svg+xml" width="154.8807 "><p>SVG-Viewer needed.</p></object></td>
</tr></table></div></div><p class="noindent">
</p><h3 class="sectionHead"><span class="titlemark">3   </span> <a id="x1-30003"/>A small graph generated by Sage</h3><p class="noindent">The Heawood graph below was created in Sage, then its latex form was requested, and the output was cut/paste
into the source of this document for processing by the tikz-graph package. It is the unique distance-regular graph
<!--l. 73--><span class="math">\Gamma </span> with intersection
array <!--l. 73--><span class="math">\left \{3,2,2;1,1,3\right \}</span>. It has
<!--l. 73--><span class="math">14</span> vertices and
spectrum <!--l. 73--><span class="math">{3}^{1}\,{(\sqrt{2})}^{6}\,{(2)}^{6}\,{(3)}^{1}</span>.
See Andries E.&#160;Brouwer&#8217;s <a href="http://www.win.tue.nl/~aeb/graphs/Heawood.html">Heawood Graph Page</a> for more information. </p><div class="center">
<!--l. 77--><p class="noindent">
                                                                                         
                                                                                         
</p><!--l. 233--><p class="noindent"><object data="graphics-test-3.svg" height="216.01755 " type="image/svg+xml" width="216.01755 "><p>SVG-Viewer needed.</p></object>
</p></div><p class="indent">   If you would prefer to see Sage&#8217;s version of this graph, execute the following code block in the worksheet version of this document. </p>

{{{id=1|
G = graphs.HeawoodGraph()
show(G)
///
}}}

<p class="indent">   In the Sage worksheet version of this document, you can rerun the code used to create the latex souce of the
tkz-graph version of this graph.
</p>

{{{id=3|
G = graphs.HeawoodGraph()
latex(G)
///
}}}

<p class="noindent">
</p><h3 class="sectionHead"><span class="titlemark">4   </span> <a id="x1-40004"/>Sage graph editor</h3><p class="noindent">Sage includes a editor that allows you to construct graphs with a point-and-click interface. The graph below was
built this way, then converted to latex and &#64257;nally pasted into the latex source of this document.
</p><div class="center">
<!--l. 254--><p class="noindent">
                                                                                         
                                                                                         
</p><!--l. 323--><p class="noindent"><object data="graphics-test-4.svg" height="216.01755 " type="image/svg+xml" width="216.01755 "><p>SVG-Viewer needed.</p></object>
</p></div><p class="indent">   In the worksheet version of this document, you can experiment with the graph editor. Construct a graph by
clicking to create new vertices. Then click one vertex to highlight it (it will become red) and then click a second
vertex to form an edge from the highlighted vertex to the second vertex. Use the same process to remove
an edge. Vertices can be deleted by dragging them outside the editing window and dropping them
there.
</p><p class="indent">   When you have the editor window available, use the&#8220;variable name&#8221; input &#64257;eld to name the graph
H.
</p>

{{{id=5|
graph_editor()
///
}}}

<p class="indent">   After saving the graph you can manipulate it with the full range of Sage commands by referencing the graph as
H. For example the commands below will give you basic information about the graph.
</p>

{{{id=7|
print "Number of vertices: ", H.num_verts()
print "Number of edges: ", H.num_edges()
print "Is connected: ", H.is_connected()
///
}}}