Half a year ago I copied together Boost examples making use of: boost/graph/make_connected.hpp boost/graph/make_biconnected_planar.hpp boost/graph/make_maximal_planar.hpp boost/graph/boyer_myrvold_planar_test.hpp boost/graph/planar_canonical_ordering.hpp boost/graph/chrobak_payne_drawing.hpp I added "read_leda_graph()" for processing graph files. And added code to write a graphiviz file from the generated straight line drawing. Use of "layout=neato" with fixated vertex coordinates with exclamation mark (pos="3,2!") misuse GraphViz to just draw the BGL determined straight line drawing. I did evaluation on random maximal planar graphs with 10,000 up to 100 million vertices in 10x steps. In 1993 I wrote a technical report on how to create maximal planar random graphs. I published the 1994 code two years ago (self written graph lib, not LEDA nor Boost): https://github.com/Hermann-SW/randomgraph All details of the evaluation including runtime table in this "straight_line_graphviz.cpp" gist comment: https://gist.github.com/Hermann-SW/99d151a273d290ee0d843c79b2da26a8?permalin... Total runtime factors are 13.5x and 20.9x between 1, 10 and 100 million vertex graphs. Since the input graphs were maximal planar, the algorithms make_connected / make_biconnected_planar and make_maximal_planar did not have much to do. The resident RAM usage is perfectly linear, 2.8 / 28.1 / 281.4 GB for 1 / 10 / 100 million vertices. 100 million vertices, 300 million edges, edge property, planar ordering, planar straight line drawing and 8 byte storage for numbers on 64bit OS cause a factor of 2800 comparing resident RAM used with number of vertices. Regards, Hermann.