I think a double-sided tree would work with the "You Are Here" node joining them. I picture parents to the left, kids to the right, all links with summary information. If disconnected components exist, list them separately by either entry point or last-visited.

Assuming you use some flavor of Graph::Base, here's a sketch:

     Viewing [Local Mutts]
                               | [Mopsy]
[Spot]  |______________________| [Rover]
[Molly] |      [ Fido ]        | [Gus]
                               | [Jack]

            [AKC Registry]
           [Fictional Dogs}
[download]

If 'Fido' is the current node, $_, then in $G (the overall graph of db keys) my @parents=$G->predecessors($_); my @kids=$G->successors($_);.

This local approach can handle circularities and self-loops as easily as the more sedate database you describe.

Update: Some corrections for Graph::Base calling conventions.

After Compline,
Zaxo