most recent 30 from http://mathoverflow.net 2013-05-21T15:06:56Z http://mathoverflow.net/feeds/question/38674 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/38674/is-the-graph-transformation-vertices-to-edges-efficiently-computable Chris Haarn 2010-09-14T11:39:06Z 2010-09-14T11:51:12Z

<p>Is this graph transformation G_1 to G_2 efficiently computable?</p> <ol> <li>All vertices in G_1 are unique edges in G_2</li> <li>Adjacent vertices in G_1 are adjacent edges in G_2</li> </ol> <p>The inverse transformation (edges to vertices) is trivial.</p> <p>I can encode it as CSP, but I am not sure solving is tractable:</p> <p>adjacent V1,V2 in G_1 to (V1',V1''), (V2',V2'') in G_2, must share a vertex, constraints: V1'=V2' \/ V1'=V2'' \/ V1''=V2' \/ V1''=V2'' and some disequations.</p> <p>References, search terms will be apreciated. Thank you.</p>

http://mathoverflow.net/questions/38674/is-the-graph-transformation-vertices-to-edges-efficiently-computable/38677#38677 Gjergji Zaimi 2010-09-14T11:51:12Z 2010-09-14T11:51:12Z

<p>This is only possible if $G_1$ is the <a href="http://en.wikipedia.org/wiki/Line_graph" rel="nofollow">line graph</a> of $G_2$. Not all graphs are line graphs.</p> <blockquote> <p>A graph $G$ is the line graph of some other graph, if and only if it is possible to find a collection of cliques in $G$, partitioning the edges of $G$, such that each vertex of $G$ belongs to at most two of the cliques.</p> </blockquote> <p><a href="http://www.sciencedirect.com/science?_ob=ArticleURL&amp;_udi=B6V0F-45FCW4T-37&amp;_user=10&amp;_coverDate=10%2F31%2F1973&amp;_rdoc=1&amp;_fmt=high&amp;_orig=search&amp;_origin=search&amp;_sort=d&amp;_docanchor=&amp;view=c&amp;_acct=C000050221&amp;_version=1&amp;_urlVersion=0&amp;_userid=10&amp;md5=bde3a2a5cadbc74f8878ccdfc7ac7989&amp;searchtype=a" rel="nofollow">Here</a> you can find am algorithm to recover the original graph from it's line graph. </p>