Embedding graphs on the projective plane

[Joshua Fallon]

Hi all, Sage rookie here. I've been working on writing functions to test whether a graph can be embedded on the projective plane, as in Myrvold and Roth's paper (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.1102&rep=rep1&type=pdf). I'm still working out some bugs, and working on transitioning from Sage functions to adding methods to the graphs class, but I think this could be a useful tool for Sage to have. My first step is a decomposition of two-connected graphs into three-blocks (cycles, cocycles, and 3-connected graphs) as described by Tutte and Cunningham and Edmonds (or call it SPQR-trees, if you like). I have this method in my local Sage source code and I think it's worthwhile to have in its own right alongside blocks_and_cuts_tree. I'd like to use this smaller method to make a first small foray into actual contribution to Sage.

Is it worth requesting a trac account now for the decomposition, or should I hold off until the whole embeddability tester is running in my local source code (assuming there's interest in that function itself)?

Best,

Joshua Fallon

[Vincent Delecroix]

Dear Joshua,

Welcome to Sage development! It is good idea to ask for a trac account
for the following reasons
* create a ticket on trac.sagemath.org that makes your project public
* upload your code changes on the git server and make your code
publicly available for discussion

Did you already have a look at the developer guide to see how all this works?

Best,
Vincent

[Joshua Fallon]

Hello Vincent,

Thank you! I did review the developer guide; the admonition there to check here for interest in a topic before requesting a trac account is what brought me here. I'll go ask for a trac account.

Best,

Joshua

[Dima Pasechnik]

On Tuesday, October 18, 2016 at 6:59:09 PM UTC+1, Joshua Fallon wrote:

Hi all, Sage rookie here. I've been working on writing functions to test whether a graph can be embedded on the projective plane, as in Myrvold and Roth's paper (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.45.1102&rep=rep1&type=pdf). I'm still working out some bugs, and working on transitioning from Sage functions to adding methods to the graphs class, but I think this could be a useful tool for Sage to have. My first step is a decomposition of two-connected graphs into three-blocks (cycles, cocycles, and 3-connected graphs) as described by Tutte and Cunningham and Edmonds (or call it SPQR-trees, if you like). I have this method in my local Sage source code and I think it's worthwhile to have in its own right alongside blocks_and_cuts_tree. I'd like to use this smaller method to make a first small foray into actual contribution to Sage.

Is it worth requesting a trac account now for the decomposition, or should I hold off until the whole embeddability tester is running in my local source code (assuming there's interest in that function itself)?

would be great to have, sure, go ahead. 

Best,

Joshua Fallon

[David Coudert]

I'll be happy to help reviewing a ticket on SPQR-trees. Definitively useful.
An option could be to interface OGDF - Open Graph Drawing Framework (http://www.ogdf.net/). It has static and dynamic implementations of SPQRtrees, but it might be too challenging for a first contribution.
David.