I need some help with an algorithm. I'm attempting to write an approximation to vertex cover using the bipartite homeograph of a planar graph but I can't figure out how to actually construct this homeograph. They make it seem simple--"just turn every face into a vertex and make an edge to its adjacent faces", but I dont see any algorithms on doing that for undirected planar graphs.
>>7932562
I can probably use the boost library's boyer myrvold planarity test to generate a planar embedding and use that in the planar face traversal, but this doesn't tell me how to get the adjacent faces for a geometric dual or even how the algorithm works
what data structure are you using for your graphs?
the algorithm to construct the homeograph certainly depends on how a graph is stored.
>>7932620
literally just an unordered set of vertices and a vector of edges, in no particular order.
I'm probably going to use boost now
>>7932562
Like a square made of triangular pyramids? :^)
>>7932624
what the hell dude, use an adjacency list. you can really efficiently find cycles (and with a little work) faces from those cycles and probably anything you are trying to do to a graph is in an intro data structures textbook.
>>7932643
The number of verts I have is too much for an adjacency matrix, thats like 750002. If you actually mean an adjacency list of edges, im doing that already
>>7932745
I mean a doubly linked list with an entry for each node where that entry is a linked list of all adjacent nodes. You don't actually have edges in there, but they are there for all intents and purposes.
https://en.wikipedia.org/wiki/Adjacency_list
>thats like 750002.
mama mia. you definitely want to choose your data structure very carefully. What you have may or may not be efficiently searchable to do what you want to do (I don't know what you mean by adjacency list of edges)
>>7932761
Yeah, I'm already doing that, since that's the format of the input. Using std::vector.
>>7932770
Ok. I don't know about your problem. You can modify topological sort to efficiently find all the cycles in your graph and maybe you could modify that to find only the cycles that correspond to a face. If you could do that then while you're doing it make a new graph out of each face as you find it.
If you think some shit in those libraries you mentioned would do it though that'd probably be a lot less of a pain in the ass.
After looking through the source here: https://github.com/aaw/boost_planar_graph_dual
I found that once you have a planar embedded version of your graph, literally all you do is create a vertex for each new face, iterate through each edge of the original graph, and create an edge to another face on the new vertex.
If the edge doesn't already exist, then create it. Otherwise.
It seems that creating the geometric dual is simple enough, but I would say that the problem I was having is not understanding how planar_face_traversal and planar_face_visitor works because the Boost documentation is so god damn fucking shit.
>>7932978
>, literally all you do is create a vertex for each new face,
how do you determine the faces though?
