Tulip  5.7.4
Large graphs analysis and drawing
OuterPlanarTest.h
1 /*
2  *
3  * This file is part of Tulip (https://tulip.labri.fr)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 
20 #ifndef OUTERPLANARTEST_H
21 #define OUTERPLANARTEST_H
22 
23 #include <tulip/tulipconf.h>
24 
25 namespace tlp {
26 
27 class Graph;
28 
29 /**
30  * @ingroup Checks
31  * @brief Provides functions to test if a graph is Outer Planar.
32  *
33  * From Wikipedia: "An OuterPlanar Graph is a graph that can be drawn in the plane without crossings
34  *in such a way that all of the vertices belong to the unbounded face of the drawing.
35  * Alternatively, a graph G is outerplanar if the graph formed from G by adding a new vertex, with
36  *edges connecting it to all the other vertices, is a planar graph."
37  **/
38 class TLP_SCOPE OuterPlanarTest {
39 public:
40  /**
41  * Returns true if the graph is outerplanar (i.e. a graph with an embedding
42  * in the plane such that all vertices belong to the unbounded face of the embedding),
43  * false otherwise.
44  */
45  /**
46  * @brief Checks if a graph is outer planar (i.e. a graph with an embedding in the plane such that
47  *all vertices belong to the unbounded face of the embedding).
48  *
49  * @param graph The graph to check.
50  * @return bool True if the graph is outer planar, false otherwise.
51  * @note this cannot be const as it uses the planarity test, which is not const and would be
52  *complex (impossible?) to make const.
53  **/
54  static bool isOuterPlanar(Graph *graph);
55 };
56 } // namespace tlp
57 
58 #endif
Provides functions to test if a graph is Outer Planar.
static bool isOuterPlanar(Graph *graph)
Checks if a graph is outer planar (i.e. a graph with an embedding in the plane such that all vertices...