Go backward to 16 Reconstruction of Simple PolytopesGo up to 3 Combinatorial StructureGo forward to 18 AOF-Orientation |
XHTML 1.0 |

Input: | The (abstract) graph G of a simple polytope _{P}P
and a family F of subsets of nodes of G_{P} |
---|---|

Output: | "Yes" if F is the family of subsets of nodes
of G that correspond to the vertex sets of the facets
of _{P}P, "No" otherwise |

Status (general): | Open |
---|---|

Status (fixed dim.): | Open |

In [32] it is shown that both the "Yes"- as well as
the "No"-answer can be proved in polynomial time in the size
of G (provided that the integrity of the input data is
guaranteed). Any polynomial time algorithm for the construction
of an AOF- or US-orientation (see Problems 18
and 19) of _{P}G would yield a polynomial time
algorithm for this problem (see [32]).
_{P}Up to dimension three the problem can be solved in polynomial time (see the comments to Problems 16 and 18). |

Related problems: | 16, 18, 19, 31 |
---|

Why are some symbols not displayed correctly? |