| dbo:abstract
|
- In graph theory, an st-planar graph is a bipolar orientation of a plane graph for which both the source and the sink of the orientation are on the outer face of the graph. That is, it is a directed graph drawn without crossings in the plane, in such a way that there are no directed cycles in the graph, exactly one graph vertex has no incoming edges, exactly one graph vertex has no outgoing edges, and these two special vertices both lie on the outer face of the graph. Within the drawing, each face of the graph must have the same structure: there is one vertex that acts as the source of the face, one vertex that acts as the sink of the face, and all edges within the face are directed along two paths from the source to the sink. If one draws an additional edge from the sink of an st-planar graph back to the source, through the outer face, and then constructs the dual graph (oriented each dual edge clockwise with respect to its primal edge) then the result is again an st-planar graph, augmented with an extra edge in the same way. (en)
- st-Планарный граф — это биполярная ориентация планарного графа, для которого как источник, так и сток ориентации находятся на внешней грани графа. То есть это ориентированный граф, нарисованный без пересечений на плоскости таким образом, что не имеется ориентированных циклов в графе, точно одна вершина графа не имеет входных дуг, точно одна вершина графа не имеет исходящих дуг, и обе эти две специальные вершины лежат на внешней грани графа. В рисунке каждая грань графа должна иметь ту же самую структуру — есть одна вершина, которая служит источником для грани, одна вершина служит стоком грани, а все рёбра внутри грани направлены вдоль двух путей от источника к стоку. Если нарисовать дополнительное ребро из стока st-планарного графа назад в источник по внешней грани и потом построить двойственный граф (ориентируя каждое двойственное ребро по часовой стрелке относительно исходного ребра), то получим снова st-планарный граф, расширенный дополнительным ребром тем же способом. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 4323 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dct:subject
| |
| gold:hypernym
| |
| rdfs:comment
|
- In graph theory, an st-planar graph is a bipolar orientation of a plane graph for which both the source and the sink of the orientation are on the outer face of the graph. That is, it is a directed graph drawn without crossings in the plane, in such a way that there are no directed cycles in the graph, exactly one graph vertex has no incoming edges, exactly one graph vertex has no outgoing edges, and these two special vertices both lie on the outer face of the graph. (en)
- st-Планарный граф — это биполярная ориентация планарного графа, для которого как источник, так и сток ориентации находятся на внешней грани графа. То есть это ориентированный граф, нарисованный без пересечений на плоскости таким образом, что не имеется ориентированных циклов в графе, точно одна вершина графа не имеет входных дуг, точно одна вершина графа не имеет исходящих дуг, и обе эти две специальные вершины лежат на внешней грани графа. (ru)
|
| rdfs:label
|
- St-planar graph (en)
- St-планарный граф (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
