Suppose we have an orthogonal polygon with holes (all walls are axis-parallel).  All vertices can be on integer coordinates, if that helps.  Partition the polygon into rectangular rooms.  I would like to find the best room to start from, to visit all the rooms (rectangles). There's a limitation on my movement: in any room, I can only leave by two directions, say north and west. (Here best means there would only be one source in the plane dual graph with directed edges showing how to walk from room to room. If more than one source is required, I wish to minimize them.) I have been looking at art gallery problems, and at VLSI papers on building rectilinear floorplans from network flows, and they are all tantalizingly close but far.  Can anyone provide suggestions so I can focus my search/proof construction?EDIT to fix problem pointed out by Peter Taylor.  I can choose two directions per room. (probably they need to be adjacent, so NE is ok but NS is not.)  If I enter one room northward, I am automatically choosing South as one of thst new room's directions. (so only two in or out directions per room)  If I choose a  direction, and there are multiple rooms adjacent in that direction, I can enter all of them (and all of them then have the reverse direction assigned as one of their two directions), so the naive greedy approach would be to choose the direction that maximizes the number of rooms I can enter at that stage. I hope this is now complete, and understandable.
Find optimal room from which to visit all other rooms in a rectangular floorplan
graph algorithms;cg.comp geom